【ZOJ2314】Reactor Cooling(有上下界的网络流)
发布时间:2020-12-15 20:36:22 所属栏目:百科 来源:网络整理
导读:前言 话说有上下界的网络流好像全机房就我一个人会 手动滑稽,当然这是不可能的 Solution 其实这道题目就是一道板子题,主要讲解一下怎么做无源无汇的上下界最大流: 算法步骤 1.将每条边转换成0~up-down。 但是,我们发现转换的时候不能保证一定是流量守恒
前言话说有上下界的网络流好像全机房就我一个人会 Solution其实这道题目就是一道板子题,主要讲解一下怎么做无源无汇的上下界最大流: 算法步骤1.将每条边转换成0~up-down。 但是,我们发现转换的时候不能保证一定是流量守恒。 2.可以把一条边的起点都减去下界,终点加上上界。令这个数组为(d) 代码实现#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<set> #include<map> #include<iostream> using namespace std; #define ll long long #define re register #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout) inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum; } const int N=210,M=200010,Inf=1e9+10; int front[N],nxt[M<<1],to[M<<1],w[M<<1],cnt,id[M<<1],n,m,d[N],ans[M<<1]; void Add(int u,int v,int val,int Id){ to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;id[cnt++]=Id; } int val[M],s,t,flow,dep[N]; void init(){ memset(front,-1,sizeof(front));cnt=0; memset(to,sizeof(to));memset(nxt,sizeof(nxt)); memset(w,sizeof(w)); } bool bfs(){ memset(dep,sizeof(dep)); queue<int >Q;while(!Q.empty())Q.pop(); Q.push(s);dep[s]=1; while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=front[u];i!=-1;i=nxt[i]){ int v=to[i]; if(!dep[v] && w[i]){ dep[v]=dep[u]+1; Q.push(v); } } } return dep[t]; } int dfs(int u,int Flow){ if(u==t || !Flow)return Flow; for(int i=front[u];i!=-1;i=nxt[i]){ int v=to[i]; if(dep[v]==dep[u]+1 && w[i]){ int di=dfs(v,min(Flow,w[i])); if(di){ w[i]-=di;w[i^1]+=di; return di; } } } return 0; } int Dinic(){ int Flow=0; while(bfs()) while(int d=dfs(s,Inf))Flow+=d; return Flow; } int main(){ int T=gi(); while(T--){ init(); n=gi();m=gi();s=0;t=n+1;memset(d,sizeof(d)); for(int i=1;i<=m;i++){ int u=gi(),v=gi(),l=gi(),c=gi(); d[u]-=l; d[v]+=l; Add(u,v,c-l,i);Add(v,u,0); val[i]=l; } for(int i=1;i<=n;i++){ if(d[i]>0){Add(s,i,d[i],0);Add(i,0);} if(d[i]<0){Add(i,-d[i],0);Add(t,0);} } flow=Dinic();bool flag=true; for(int i=front[s];i!=-1;i=nxt[i]) if(w[i]>0){flag=false;break;} if(!flag)puts("NO"); else{ puts("YES"); for(int i=0;i<cnt;i++)ans[id[i]]=w[i^1]; for(int i=1;i<=m;i++) printf("%dn",ans[i]+val[i]); } puts(""); } return 0; }f (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |