ZOJ [P2314] 无源汇点有上下界模版

对于有上下界的网络流来说,我们可以分离出必要弧,然后将必要弧切开,两端分别连接源点和汇点,原图有可行解充要于源点或汇点满流.

这样求下来,只能求出可行流

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <queue>

using namespace std;

int n,m,s,t,head[250],cur[250],dep[250],nume;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

struct edge{

	int to,nxt,cap,flow;

}e[500005];

void adde(int from,int to,int cap){

	e[++nume].to=to;

	e[nume].cap=cap;

	e[nume].nxt=head[from];

	head[from]=nume;

	e[nume].flow=0;

}

bool bfs(){

	queue<int> q;

	while(!q.empty()) q.pop();

	memset(dep,0,sizeof(dep));

	q.push(s);

	dep[s]=1;

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			if(!dep[v]&&(e[i].flow<e[i].cap)){

				dep[v]=dep[u]+1;

				q.push(v);

			}

		}

	}

	if(dep[t])	return 1;

	else return 0;

}

int dfs(int u,int flow){

	if(u==t) return flow;

	int tot=0;

	for(int &i=cur[u];i&&tot<flow;i=e[i].nxt){

		int v=e[i].to;

		//printf("%d %d\n",v,e[i].cap-e[i].flow);

		if((dep[v]==dep[u]+1)&&(e[i].flow<e[i].cap)){

			if(int t=dfs(v,min(flow-tot,e[i].cap-e[i].flow))){

				e[i].flow+=t;

				//cout<<t<<endl;

				e[((i-1)^1)+1].flow-=t;

				tot+=t;

			}

		}

	}

	return tot;

}

int dinic(){

	int ans=0;

	while(bfs()){

		for(int i=1;i<=n+2;i++) cur[i]=head[i];

		ans+=dfs(s,0x3f3f3f3f);

	}

	return ans;

}

int main(){

	int T=init();

	while(T--){

		int tot=0,ans=0;

		n=init();m=init();

		s=n+2;t=n+1;

		memset(head,0,sizeof(head));

		nume=0;

		for(int i=1;i<=m;i++){

			int u=init(),v=init(),b=init(),d=init();

			adde(u,v,d-b);

			adde(v,u,0);

			adde(s,v,b);//千万不要建反

			adde(v,s,0);

			adde(u,t,b);

			adde(t,u,0);

			tot+=b;

		}

		ans=dinic();

	//	for(int i=head[s];i;i=e[i].nxt) cout<<e[i].to<<endl;

		if(ans<tot) printf("NO\n");

		else{

			printf("YES\n");

			for(int i=1;i<=nume;i+=6){

				printf("%d\n",e[i].flow+e[i+2].cap);

			}

		}

		printf("\n");

	}

	return 0;

}

巴特西

ZOJ [P2314] 无源汇点有上下界模版

最新文章

热门文章