acdream 1211 Reactor Cooling 网络流

传送门:acdream 1211

给定n个点,以及它们之间的m个管道,每个管道有流量的最小限制和最大限制,问能否存在一种情况,使得所有管道内的流量都满足流量限制

带上下界的网络流,如果不考虑流量的最小限制,那就是单纯的网络流问题,因此这里只需要转化一下即可。

对于每一条管道,将最小限制加到入口的出度,加到出口的入度,求出所有点的总入度与总出度,总入度大的,建立一个源点指向该点,流量即为该点入度与出度之差,总出度大的,该点建一条边指向一个汇点,流量为出度与入度之差,然后每条管道的流量限制都更新为最大流量与最小流量之差,对于建立的新图跑一遍网络流,如果是汇源满流则说明可行,每条管道的流量即为新图的当前流量与该管道的最小流量限制之和。

/******************************************************
 * File Name:   b.cpp
 * Author:      kojimai
 * Creater Time:2014年10月01日 星期三 16时00分06秒
******************************************************/

#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define FFF 205
int first[FFF],in[FFF],e,dis[FFF];
struct node
{
	int v,f,l,next;
}edge[50005];
void addedge(int x,int y,int l,int c)
{
	edge[e].v=y;edge[e].next=first[x];edge[e].l=l;edge[e].f=c;first[x]=e++;
	edge[e].v=x;edge[e].next=first[y];edge[e].l=0;edge[e].f=0;first[y]=e++;
}
bool bfs(int s,int t)
{
	memset(dis,-1,sizeof(dis));
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int now = q.front();q.pop();
		for(int k = first[now];k!=-1;k = edge[k].next)
		{
			if(edge[k].f-edge[k].l>0 && dis[edge[k].v] ==-1)
			{
				dis[edge[k].v] = dis[now] + 1;
				if(edge[k].v == t)
					return true;
				q.push(edge[k].v);
			}
		}
	}
	return false;
}
int dfs(int now,int flow,int t)
{
	int f;
	if(now == t)
		return flow;
	for(int k = first[now];k != -1;k = edge[k].next)
	{
		if(edge[k].f - edge[k].l > 0 && dis[edge[k].v] == dis[now] + 1 && (f=dfs(edge[k].v,min(flow,edge[k].f - edge[k].l),t)))
		{
			edge[k].f -= f;
			edge[k^1].f += f;
			return f;
		}
	}
	return 0;
}
int dinic(int s,int t)
{
	int flow,ret = 0;
	while(bfs(s,t))
	{
		while(flow=dfs(s,233333333,t))
			ret += flow;
	}
	return ret;
}
int main()
{
	int n,m,x,y,c;
	while(~scanf("%d%d",&n,&m))
	{
		memset(first,sizeof(first));
		memset(in,sizeof(in));
		e=0;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d%d",&x,&y,&l,&c);
			addedge(x,c);
			in[x]-=l;in[y]+=l;
		}
		int sum = 0;
		for(int i=1;i<=n;i++)
		{
			if(in[i]>0)
			{
				addedge(0,i,in[i]);
				sum += in[i];
			}
			else if(in[i]<0)
				addedge(i,n+1,-in[i]);
		}
		int ans = dinic(0,n+1);
		if(sum == ans)
		{
			printf("YESn");
			for(int i=0;i<m;i++)
				printf("%dn",edge[i*2].l+edge[i*2+1].f);
		}
		else
			printf("NOn");
	}
	return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!