首页 > 代码库 > zoj2314 Reactor Cooling --- 上下界可行流
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]; } else solve.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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。