本文共 827 字,大约阅读时间需要 2 分钟。
求连通块,因为一个连通块上的顶点在经过无数次传递之后肯定能经过同一个点,所以就求出连通块的数目,然后计算,然后累加前m大的即可。
#include#include #include #include using namespace std;typedef long long ll;const int maxn=1e5+5;int n,m;int a[maxn];int b[maxn];int c[maxn];ll num[maxn];int ci;int Find (int x){ if(a[x]==x) return x; return a[x]=Find(a[x]);}int main(){ memset (num,0,sizeof(num)); scanf("%d%d",&n,&m); ci=n; for (int i=1;i<=n;i++) a[i]=i; for (int i=1;i<=n;i++) { scanf("%d",&b[i]); } for (int i=1;i<=n;i++) { scanf("%d",&c[i]); int pa=Find(i); int pb=Find(c[i]); if(pa!=pb) { a[pa]=pb; ci--; } } ll ans=0; for (int i=1;i<=n;i++) { num[Find(i)]+=b[i]; } sort(num+1,num+n+1); for (int i=0;i
转载地址:http://uwoen.baihongyu.com/