Pjudge #21614. 守卫/2021-2022 ICPC North America Championships. Problem I

本文主要是介绍Pjudge #21614. 守卫/2021-2022 ICPC North America Championships. Problem I，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
首先显然是在最小生成树上搞的。
可以发现，如果有\(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));
}

这篇关于Pjudge #21614. 守卫/2021-2022 ICPC North America Championships. Problem I的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！