Dinic求助,找不到问题
查看原帖
Dinic求助,找不到问题
124918
LinkyChristian楼主2021/10/27 01:19

如题,代码剩下20pt

#include<bits/stdc++.h>
#define N 80010
#define M 1000010
using namespace std;
int x,y,cnt,head[N],to[M],nxt[M],val[M];
void insert(int u,int v,int w) {
	cnt++;
	to[cnt]=v;
	val[cnt]=w;
	nxt[cnt]=head[u];
	head[u]=cnt;
} 
void Insert(int u,int v,int w) {
	insert(u,v,w);
	insert(v,u,0);
} 
int n1,n2,n3,m1,m2,s,t;
int dep[N],cur[N];
int bfs() {
	queue<int> q;
	memset(dep,0,sizeof(dep));
	dep[s]=1,q.push(s);
	while(!q.empty()) {
		int now=q.front();q.pop();
		for(int i=head[now]; i; i=nxt[i])
		    if((!dep[to[i]])&&(val[i]>0)) 
		    	dep[to[i]]=dep[now]+1,
		    	q.push(to[i]);
	}
	return (dep[t]>0);
}
int dfs(int now,int dis) {
	if(now==t) return dis;
	for(int& i=cur[now]; i; i=nxt[i]) 
	    if(dep[to[i]]==dep[now]+1&&(val[i]>0)) {
	    	int res=dfs(to[i],min(dis,val[i]));
	    	if(res>0) {
	    		val[i]-=res,val[i^1]+=res;
	    		return res;
			}
		}
	return 0;
}
int Dinic() {
	int ans=0;
	while(bfs()) {
		for(int i=0; i<=t; i++) cur[i]=head[i];
		while(int dis=dfs(s,0x3f3f3f3f)) ans+=dis;
	}
	return ans;
}
int main()
{
	cin>>n1>>n2>>n3;
	t=2*n1+n2+n3+1;
	cin>>m1;
	for(int i=1; i<=m1; i++) {
		cin>>x>>y;
		Insert(y,n2+x,1);
	}
	cin>>m2;
	for(int i=1; i<=m2; i++) {
		cin>>x>>y;
		Insert(n2+n1+x,n2+2*n1+y,1);
	}
	for(int i=1; i<=n1; i++) Insert(n2+i,n2+n1+i,1);
	for(int i=1; i<=n2; i++) Insert(s,i,1);
	for(int i=1; i<=n3; i++) Insert(n2+2*n1+i,t,1);
	cout<<Dinic();
}
2021/10/27 01:19
加载中...