萌新求助网络流建模,WA on#6#7
查看原帖
萌新求助网络流建模,WA on#6#7
238408
vectorwyxSD省选加油楼主2021/1/8 10:44

RT,下载下来的数据有点大,想不通哪里错了。谢谢诸位巨佬QAQ

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue> 
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=1005,M=50005;
struct Edge{
	int to,next,c,r;
}e[M];
int head[N],tot=1,now[N],d[N],S,T,n,f,dd;

void connect(int x,int y,int v,int _v){
	e[++tot]=(Edge){y,head[x],v,_v};
	head[x]=tot; 
}

bool bfs(){
	memset(d,0,sizeof d);
	queue<int> q;
	d[S]=1;
	for(int i=head[S];i;i=e[i].next){
		if(e[i].r<=0) continue;
		int p=e[i].to;
		d[p]=2;
		now[p]=head[p];
		q.push(i); 
	}
	while(!q.empty()){
		int x=q.front(),y=e[x].to;q.pop();
		if(y==T) return 1;
		for(int i=head[y];i;i=e[i].next){
			int p=e[i].to;
			if(d[p]||e[i].r<=0) continue;
			d[p]=d[y]+1;
			q.push(i);
			now[p]=head[p]; 
		}
	}
	return 0;
}

int dfs(int x,int lim){
	if(x==T) return lim;
	int ret=0;
	for(int i=now[x];i;i=e[i].next){
		int p=e[i].to;
		if(d[p]!=d[x]+1||e[i].r<=0) continue;
		now[x]=i;
		int w=min(lim,e[i].r),k=dfs(p,w);
		lim-=k;
		ret+=k;
		e[i].r-=k,e[i^1].r+=k;
		if(lim==0) break;
	}
	return ret;
}

int main(){
	cin>>n>>f>>dd;
	fo(i,1,n){
		connect(f+i,f+n+i,1,1);
		connect(f+n+i,f+i,0,0);
		int fi=read(),di=read();
		fo(j,1,fi){
			int x=read();
			connect(x,i+f,1,1);
			connect(i+f,x,0,0);
		}
		fo(j,1,di){
			int x=read(),xx=i+f+n,yy=x+f+2*n;
			connect(xx,yy,1,1);
			connect(yy,xx,0,0);
		}
	}
	S=f+2*n+dd+1,T=S+1;
	fo(i,1,f) connect(S,i,1,1),connect(i,S,0,0);
	fo(i,1,dd) connect(i+f+2*n,T,1,1),connect(T,i+f+2*n,0,0);
	int ans=0;
	while(bfs()){
		for(int i=head[S];i;i=e[i].next){
			if(e[i].r<=0) continue;
			ans+=dfs(e[i].to,e[i].r);
		}
	}
	cout<<ans;
	return 0;
}
/*
-------------------------------------------------
*/
2021/1/8 10:44
加载中...