题目概述

CF1408E

解题报告

呜呜呜，这就是个沙雕题，但是我不会。

如果多个集合之间的边组成了环说明就有彩虹路，但是显然我们不可能把一个集合中的所有边建出来。

考虑建辅助点，自然而然我们想到对于每个集合建一个点作为辅助点，然后把所有集合中的点连向辅助点，在这张图中出现环说明有彩虹路。

因此我们只要选出一棵最大生成树就好了……

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000,maxt=200000,maxm=200000;

int n,m,a[maxn+5],b[maxn+5],fat[maxt+5];LL ans;
int E;pair<int, pair<int,int> > e[maxm+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
int main(){
    freopen("E.in","r",stdin);freopen("E.out","w",stdout);
    readi(m);readi(n);
    for (int i=1;i<=m;i++) readi(a[i]),fat[i]=i;
    for (int i=1;i<=n;i++) readi(b[i]),fat[i+m]=i+m;
    for (int i=1;i<=m;i++){
        int A,x;readi(A);
        for (int j=1;j<=A;j++)
            readi(x),e[++E]=mp(-a[i]-b[x],mp(i,x+m)),ans+=a[i]+b[x];
    }
    sort(e+1,e+E+1);
    for (int i=1;i<=E;i++){
        int x=getfa(e[i].sc.fr),y=getfa(e[i].sc.sc);
        if (x==y) continue;fat[x]=y;ans+=e[i].fr;
    }
    printf("%lld\n",ans);return 0;
}