E.Avoid Rainbow Cycles 题意： 有m个集合，n个点，每个集合有一些1到n的数，这些数代表的点构成一个完全图，边的颜色为i（第i个集合），然后定义彩虹环是一个环，这个环上的所有边都是不同颜色的，每次操作可以删除一个集合中的一个点，花费为a[i]+b[j]，代表第i个集合的第j点，求最小花费使得最终不存在彩虹环。 思路: 这个题很难下手，因为彩虹环定义和完全图这些东西太绕了，但是其实可以定义一个点n+i，连着第i集合中的所有点，这样其实也就成了完全图，就抽象为了某个点，经过第n+i个点(即i颜色的边)到达另一个点，这个和克鲁斯重构树差不多，把边化为点，然后这样的话最终一定得是个树才行，否则只要有环，则一定是存在彩虹环，因为点和点之间没有任何连边，所以这个图一定是点-边-点-边这种的形式，所以出现了环，则某个点一定是连接了至少两个不同颜色边，因此肯定出现了彩虹环，因此题目就可以转化为求最小花费使得这个图变成一棵树，这样就可以变成了最大生成树问题。 总结：如果碰到了这种的完全图问题，可以建立一个总点，这样就可以简化图了，从而使得模型更加清晰简约，这个题稍微有些重构树的思想，这种模型确实很神奇。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int MAX_N=101000; long long a[MAX_N],b[MAX_N]; struct skt{ int x,y; long long z; }edge[2*MAX_N]; int pre[2*MAX_N]; bool cmp(skt a,skt b){ return a.z>b.z; } int find(int x){ if(pre[x]!=x) pre[x]=find(pre[x]); return pre[x]; } int main(void){ int n,m,i,j,k; scanf("%d%d",&m,&n); for(i=1;i<=m;i++) scanf("%lld",&a[i]); for(i=1;i<=n;i++) scanf("%lld",&b[i]); for(i=1;i<=n+m;i++) pre[i]=i; int cnt=0; long long res=0; for(i=1;i<=m;i++){ int x; scanf("%d",&k); for(j=1;j<=k;j++){ scanf("%d",&x); edge[++cnt].x=n+i,edge[cnt].y=x,edge[cnt].z=a[i]+b[x]; res+=edge[cnt].z; } } sort(edge+1,edge+cnt+1,cmp); for(i=1;i<=cnt;i++){ int x=edge[i].x,y=edge[i].y; long long z=edge[i].z; int fx=find(x),fy=find(y); if(fx!=fy){ pre[fx]=fy; res-=z; } } printf("%lld\n",res); return 0; }