本文主要是介绍zoj2314 Reactor Cooling --- 上下界可行流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目给出了每条边的上下界，
此类题目的建边方法是：
1、添加源点汇点，
2、对每条边 添加边 c(u,v) = up(u,v) - low(u,v)
3、对每个点 c(s,v) = out(v)
c(v,t) = in(v) (权值为正)
求s到t的最大流，若最大流等于所有边下界的和，则存在可行流，
每条边的流量为 flow(u,v) +low(u,v)
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll __int64
const int maxn=210;
const int maxm=40010;
using namespace std;int n,m,s,t,low[maxm],in[maxn],out[maxn];
struct node
{int from,to,cap,flow;
};
struct dinic
{int n,m,s,t;vector<node> e;vector<int> g[maxn];bool vis[maxn];int d[maxn];int cur[maxn];void init(int n){e.clear();for(int i=0;i<=n+1;i++)g[i].clear();}void addedge(int a,int b,int c,int d)//c d为正向弧和反向弧的权值 一般反向弧为0{e.push_back((node){a,b,c,0});e.push_back((node){b,a,d,0});m=e.size();g[a].push_back(m-2);g[b].push_back(m-1);}bool bfs(){memset(vis,0,sizeof vis);queue<int> q;q.push(s);d[s]=0;vis[s]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<g[x].size();i++){node& ee=e[g[x][i]];if(!vis[ee.to]&&ee.cap>ee.flow){vis[ee.to]=1;d[ee.to]=d[x]+1;q.push(ee.to);}}}return vis[t];}int dfs(int x,int a){if(x==t||a==0) return a;int flow=0,f;for(int& i=cur[x];i<g[x].size();i++){node& ee=e[g[x][i]];if(d[x]+1==d[ee.to]&&(f=dfs(ee.to,min(a,ee.cap-ee.flow)))>0){ee.flow+=f;e[g[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0) break;}}return flow;}int maxflow(int s,int t){this->s=s;this->t=t;int flow=0;while(bfs()){memset(cur,0,sizeof cur);flow+=dfs(s,inf);}return flow;}void output(int cnt){for(int i=0;i<cnt;i++)printf("%d\n",e[i*2].flow+low[i]);}
};
dinic solve;int main()
{int icy,a,b,cc,d,i,full;scanf("%d",&icy);while(icy--){scanf("%d%d",&n,&m);s=0,t=n+1;solve.init(n);memset(in,0,sizeof in);memset(out,0,sizeof out);for(i=0;i<m;i++){scanf("%d%d%d%d",&a,&b,&low[i],&d);solve.addedge(a,b,d-low[i],0);out[a]+=low[i];in[b]+=low[i];}full=0;for(i=1;i<=n;i++){if(out[i]<in[i]){solve.addedge(s,i,in[i]-out[i],0);full+=in[i]-out[i];}elsesolve.addedge(i,t,out[i]-in[i],0);}if(solve.maxflow(s,t)!=full)printf("NO\n");else{printf("YES\n");solve.output(m);}}return 0;
}
这篇关于zoj2314 Reactor Cooling --- 上下界可行流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
