蓝桥杯2020年第十一届省赛真题-网络分析

解题思路:并查集加懒惰标记

注意事项:注意标记清零。

参考代码:

#include<iostream>
#include<unordered_map>
#include<vector>
#include<deque>
#include<algorithm>
#include<map>
#include<set>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
//#define int  long long

using namespace std;
typedef  long long ll;
const int N=1e5+10;
int n,m;
int idx,head[N],w[N],e[N],ne[N],p[N],cnt[N],st[N],p1[N];

inline int read()
{
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}


void init(){
    memset(head,-1,sizeof(head));
    idx=0;
}

void add(int a,int b){
    e[idx]=b;
    ne[idx]=head[a];
    head[a]=idx++;
}

int find(int a){
    if(a!=p[a]) p[a]=find(p[a]);
    return p[a];
}

void bfs1(int u){
    //cout<<"cnt = "<<cnt[u]<<" u = "<<u<<endl;
    w[u]+=cnt[u];
    for(int i=head[u];~i;i=ne[i]){
        int k=e[i];
        cnt[k]+=cnt[u];
    }
    cnt[u]=0;
}

void bfs(int u){
    //cout<<"u = "<<u<<endl;
    queue<int>q;
    q.push(u);
    w[u]+=cnt[u];
    memset(st,0,sizeof st);
    st[u]=1;
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=head[t];i!=-1;i=ne[i]){
            int k=e[i];
            if(!st[k]){
                cnt[k]+=cnt[t];
                st[k]=1;
                w[k]+=cnt[k];
                q.push(k);
                //cnt[k]=0;
            }
        }
    }
    cnt[u]=0;
}


void solve(){
    init();
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--){
        scanf("%d %d %d",&a,&b,&c);
        if(a==1){
            if(find(b)==find(c)) continue;
            if(cnt[p[c]]){
                bfs1(p[c]);
            }
            if(cnt[p[b]]){
                bfs1(p[b]);
            }
            add(p[b],p[c]),add(p[c],p[b]);
//            if(cnt[(find(c))]){
//                bfs(find(c));
//            }
//            if(cnt[find(b)]){
//                bfs(find(b));
//            }
            p[p[b]]=p[c];
//            add(b,c),add(c,b);
        }
        if(a==2){
            cnt[find(b)]+=c;
        }
    }
    for(int i=1;i<=n;i++){
        if(0==p1[find(i)]){
            p1[p[i]]=1;
            bfs(p[i]);
        }
        printf("%d ",w[i]+cnt[find(i)]);
        //else cout<<w[i]<<endl;
    }
}

signed main(){
    int t=1;
    //cin>>t;
    while(t--) solve();
}