题面传送门
首先显然是在最小生成树上搞的。
可以发现,如果有\(k_1,k_2\dots k_m\)这些村庄被派遣了守卫,那么被断掉的边一定是两两点对间的最大边,容易证明这只有\(k-1\)条。
不难想到建立Kruskal重构树,然后一个额外点要选的话那么两个儿子中都有守卫。
我们将守卫看作流,那么对于每个节点,先保证往上,再走选择这条边。
因为Kruskal重构树具有单调性,可以发现本来它自己就会往上流,只要在最高的节点连到T点一条inf的边就好了。
然后跑个最大费用最大流就好了,-1的边界仔细判判。
code:
#include<bits/stdc++.h> #define I inline #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define abs(x) ((x)>0?(x):-(x)) #define ll long long #define db double #define lb long db #define N (300+5) #define M (900+5) #define K (200000+5) #define mod 9248440332 #define Mod (mod-1) #define eps (1e-9) #define U unsigned int #define it iterator #define Gc() getchar() #define Me(x,y) memset(x,y,sizeof(x)) #define Mc(x,y) memcpy(x,y,sizeof(x)) #define d(x,y) (n*(x-1)+(y)) #define R(n) (rand()*rand()%(n)+1) #define Pc(x) putchar(x) #define LB lower_bound #define UB upper_bound #define PB push_back using namespace std; int Fl[N],n,m,k,x,y,z,fa[M],W[M],S,T,cnt,Ans; struct Ques{int x,y,z;}Q[N*N];I bool cmp(Ques x,Ques y){return x.z<y.z;} I int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;} struct yyy{int to,g,w,z;};struct ljb{int head=1,h[M+5];yyy f[M*M+5];I void add(int x,int y,int g,int w){f[++head]=(yyy){y,g,w,h[x]};h[x]=head;}}s; I void Ins(int x,int y,int g,int w){s.add(x,y,g,w);s.add(y,x,0,-w);} namespace EK{ int pre[M],g[M],d[M],Ans,ToT;queue<int> Q;yyy tmp;I int bfs(){ Q.push(S);Me(d,-0x3f);g[S]=1e9;d[S]=0;while(!Q.empty()){ x=Q.front();Q.pop();for(int i=s.h[x];i;i=tmp.z){ tmp=s.f[i];if(d[tmp.to]>=d[x]+tmp.w||!tmp.g) continue;;g[tmp.to]=min(g[x],tmp.g);d[tmp.to]=d[x]+tmp.w;pre[tmp.to]=i;Q.push(tmp.to); } }return d[T]>=0; }I int calc(){while(bfs()) {Ans+=g[T]*d[T];ToT+=g[T];for(x=T;x^S;x=s.f[pre[x]^1].to) s.f[pre[x]].g-=g[T],s.f[pre[x]^1].g+=g[T];}if(ToT^k){puts("-1");exit(0);}return Ans;} } int main(){ freopen("1.in","r",stdin); int i;scanf("%d%d%d",&n,&m,&k);for(i=1;i<=m;i++) scanf("%d%d%d",&Q[i].x,&Q[i].y,&Q[i].z);sort(Q+1,Q+m+1,cmp); cnt=n;for(i=1;i<=2*n;i++) fa[i]=i;for(i=1;i<=m;i++) GF(Q[i].x)^GF(Q[i].y)&&(W[++cnt]=Q[i].z,Ans+=Q[i].z,Ins(GF(Q[i].x),cnt,1,0),Ins(GF(Q[i].y),cnt,1,0),fa[GF(Q[i].x)]=fa[GF(Q[i].y)]=cnt); S=0;T=k+cnt+1;for(i=1;i<=k;i++) {Ins(S,cnt+i,1,0);scanf("%d",&x);while(x--) scanf("%d",&y),Fl[y]=1,Ins(cnt+i,y,1,0);}for(i=n+1;i<=cnt;i++) Ins(i,T,1,W[i]);for(i=1;i<=cnt;i++)GF(i)==i&&(Ins(i,T,1,1e7),0); for(i=1;i<=n;i++) Fl[GF(i)]|=Fl[i];for(i=1;i<=cnt;i++) if(GF(i)==i&&!Fl[i]&&n^1){puts("-1");return 0;} printf("%d\n",Ans-EK::calc()%(10000000)); }