题目链接：点击查看
题目大意：给出 m 个集合，每个集合中都有数个点，每个点的取值范围为 [ 1 , n ] ，对于每个集合而言，其中的点互相连边，边的颜色为其集合的编号，每次操作可以删除点，删除掉第 i 个集合中的点 j 的代价为 a[ i ] + b[ j ] ，现在规定 “彩虹环” 的定义为，一条环上的所有边的编号互不相同，现在问最少花费多少边权进行删点才能使得图中不存在 “彩虹环”
题目分析：模型的话很像之前训练的时候做过的一个最短路，也是好多个集合，每个集合中的点互相连边：HDU - 5521
于是不难想到对于每个集合而言，建立一个虚拟节点来表示此集合中的点两两可达，又因为题目中给出了删除掉每个节点的权值，所以虚拟节点与每个节点相连后的边权就是相应的 a[ i ] + b[ j ] 了
现在考虑转换最终的问题，也就是不存在 “彩虹环” 代表的到底是什么，因为经过了上一段的建模后，新的模型的特点是：
每个集合中的任意两点都是可达的每个集合中不存在环这样在新图中，如果存在环的话，那么一定是来自于不同集合的边所造成的贡献，所以我们只需要进行删边，使得新图中不存在环即可
因为要求删除的边权最小，换个角度就是剩下的树的权值尽可能大，这样题目就转换成了最大生成树的问题了
代码：
//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=2e5+100; struct Edge { int u,v; LL w; bool operator<(const Edge& t)const { return w>t.w; } }edge[N]; int cnt=0; LL a[N],b[N]; int f[N<<1]; int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } bool merge(int x,int y) { int xx=find(x),yy=find(y); if(xx!=yy) { f[xx]=yy; return true; } return false; } void init() { for(int i=0;i<N<<1;i++) f[i]=i; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false); init(); int m,n; LL ans=0; scanf("%d%d",&m,&n); for(int i=1;i<=m;i++) scanf("%lld",a+i); for(int i=1;i<=n;i++) scanf("%lld",b+i); for(int i=1;i<=m;i++) { int num; scanf("%d",&num); while(num--) { int x; scanf("%d",&x); cnt++; edge[cnt].u=i+n; edge[cnt].v=x; edge[cnt].w=a[i]+b[x]; ans+=a[i]+b[x]; } } sort(edge+1,edge+1+cnt); for(int i=1;i<=cnt;i++) if(merge(edge[i].u,edge[i].v)) ans-=edge[i].w; printf("%lld\n",ans); return 0; }
