题解 CF1408E 【Avoid Rainbow Cycles】

· · 题解

删掉的权值最小，考虑转化为保留的权值最大。

把集合和数字都看成点，集合里有数字就把这个数字往集合连边，求最大生成树即可。

不难发现这个最大生成树的权值可以达到，并且如果出现环，那么必然会有 rainbow cycle .

证明 : 如果这张图上存在环，那么我们考虑一个环

如果这上面有相同的集合，那么就把它们缩起来，这个环显然还是存在的，并且因为有环，所以我们在缩边的时候**一定能保证环内仍然有 $\geq 2$ 个不同的集合.** $Kruskal$ 即可。 $\Theta((n+m)\log (n+m))

code :

#include <bits/stdc++.h>
#define LL long long
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(LL x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int N = 100005;
struct Union_Find_Set{
    int fa[N<<1];
    inline void init(){ for (int i = 1; i <= 200000; ++i) fa[i] = i; }
    inline int Find(int x){ return x == fa[x] ? x : (fa[x] = Find(fa[x])); }
    inline bool Merge(int x,int y){ x = Find(x),y = Find(y); if (x == y) return 0; fa[x] = y;  return 1; }
}S;
int n,m,a[N],b[N]; LL ans;
struct Edge{ int x,y,z; bool operator < (const Edge w) const{ return z > w.z; } }e[N+N]; int le;
int main(){
    int i,t,x;
    S.init();
    read(m),read(n); 
    for (i = 1; i <= m; ++i) read(a[i]);
    for (i = 1; i <= n; ++i) read(b[i]);
    for (i = 1; i <= m; ++i){
        read(t);
        while (t--) ++le,read(x),e[le].x = x,e[le].y = i+n,e[le].z = a[i] + b[x],ans += e[le].z;
    }
    sort(e+1,e+le+1);
    for (i = 1; i <= le; ++i) if (S.Merge(e[i].x,e[i].y)) ans -= e[i].z;
    write(ans),putchar('\n');
    return 0;
}