WA求助
查看原帖
WA求助
556362
Unnamed114514楼主2023/7/19 17:31
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define add(u,v,w) add_edge(u,v,w),add_edge(v,u,0)
using namespace std;
const int N=1e2+100,M=2e4+100;
int n,m,S,T,s,t,tot,q[N],l,r,c[M],now[N],to[M],head[N],nxt[M],d[N],dep[N];
inline bool bfs(int s){
	memset(dep,0,sizeof(dep));
	q[l=r=1]=s,dep[s]=1,now[s]=head[s];
	while(l<=r){
		int u=q[l++];
		for(int h=head[u];h;h=nxt[h]){
			if(!dep[to[h]]&&c[h]){
				dep[to[h]]=dep[u]+1;
				now[to[h]]=head[to[h]];
				if(to[h]==t)
					return 1;
				q[++r]=to[h];
			}
		}
	}
	return 0;
}
int dfs(int u,int F){
	if(u==t)
		return F;
	int rest=F;
	for(int h=now[u];h&&rest;h=nxt[h]){
		now[u]=h;
		if(c[h]&&dep[to[h]]==dep[u]+1){
			int o=dfs(to[h],min(rest,c[h]));
			if(!o)
				dep[to[h]]=0;
			c[h]-=o,c[h^1]+=o;
			rest-=o;
		}
	}
	return F-rest;
}
inline int dinic(){
	int ans=0,delta;
	while(bfs(s))
		while(delta=dfs(s,inf))
			ans+=delta;
	return ans;
}
inline void add_edge(int u,int v,int w){
	++tot,nxt[tot]=head[u],head[u]=tot,to[tot]=v,c[tot]=w;
} 
int main(){
	scanf("%d",&n);
	s=n+1,t=n+2,S=n+3,T=n+4;
	for(int i=1,m,x;i<=n;++i){
		add(s,i,inf);
		add(i,t,inf);
		scanf("%d",&m);
		while(m--){
			scanf("%d",&x);
			add(i,x,inf);
			++d[x],--d[i];
		}
	}
	for(int i=1;i<=n;++i){
		if(d[i]>0)
			add(s,i,d[i]);
		if(d[i]<0)
			add(i,t,-d[i]);
	}
	dinic();
	int flow=0;
	s=T,t=S;
	for(int i=head[s];i;i=nxt[i])
		if(to[i]==T){
			flow=c[i];
			c[i]=c[i^1]=0;
		}
	cout<<flow-dinic()<<endl;
	return 0;
}
2023/7/19 17:31
加载中...