牛客练习赛 68 69 C题 无向图并查集

练习赛 68 69 C题 无向图并查集"/>

牛客练习赛 68 69 C题 无向图并查集

一开始看到这道题，想到的是最短路，用dijkstra，但是n的范围太大了，直接超内存，看了题解之后发现是并查集的思路。
先存点，用node存上{u,v,w}，根据权值来降序，判断两点是不是一个祖先，如果不是一个祖先，答案加上两点间的权值。
这就相当于先找最大权值两点相连的点，这两点直接的权值就确定下来了，接下来只是在m条边中找其它两点的权值，直到所有的边完成遍历。答案就是所有边的最大权值。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M=1e5+5;
int f[5*M];
struct node{int u,v;ll w;
}a[5*M];
bool cmp(node a,node b){return a.w>b.w;
}
int find(int a){if(a!=f[a]) f[a]=find(f[a]);return f[a];
}
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){f[i]=i;}for(int i=0;i<m;i++){scanf("%d%d%lld",&a[i].u,&a[i].v,&a[i].w);}sort(a,a+m,cmp);ll ans=0;for(int i=0;i<m;i++){if(find(a[i].u)==find(a[i].v)) continue;f[find(a[i].u)]=f[find(a[i].v)];ans+=a[i].w;}printf("%lld",ans);return 0;
}

这题搞完了之后，又想到了上一次的练习赛，也有一道类似的题。

再学一下Kruskal算法

#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define maxn 500005
#define ll long long
unsigned int SA,SB,SC;
int n,m,q,LIM;
ll f[M];
ll L[maxn],ans[M];
ll choose[M],num[maxn];
ll th=n,sh=0;
struct node{ll u,v,w;
}maps[maxn];
bool cmp(node a,node b){return a.w<b.w;
}
unsigned int rng61(){SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;unsigned int t=SA;SA=SB;SB=SC;SC^=t^SA;return SC;
}
void gen(){scanf("%d%d%d%u%u%u%d",&n,&m,&q,&SA,&SB,&SC,&LIM);for(int i=1;i<=m;i++){maps[i].u=rng61()%n+1;maps[i].v=rng61()%n+1;maps[i].w=rng61()%LIM;}for(int i=1;i<=q;i++){L[i]=rng61()%LIM;}
}
ll find(ll x){if(f[x]==x) return x;else return f[x]=find(f[x]);
}
ll bs(ll k){ll l=0,r=sh;while(l<r){ll mid=(l+r+1)/2;if(choose[mid]>k) r=mid-1;else l=mid;}return num[l];
}
int main(){gen();sort(maps+1,maps+m+1,cmp);for(int i=1;i<=n;i++){f[i]=i;ans[i]=1;}num[0]=0;th=n,sh=0;for(int i=1;i<=m&&th>1;i++){int du=find(maps[i].u),dv=find(maps[i].v);if(du==dv) continue;else{th--;sh++;f[dv]=du;num[sh]=num[sh-1]+1ll*ans[du]*ans[dv];ans[du]+=ans[dv];choose[sh]=maps[i].w;}}ll res=0;for(int i=1;i<=q;i++){res^=bs(L[i]);}printf("%lld\n",res);return 0;
}