zoj 2314 Reactor Cooling

题意：网络中，每一条边拥有流量上限和下限，问是否存在可行流。

思路：最大流（经典模型，建图）。这个模型的建图方法略为神奇，原图中，边的容量改为流量上限-流量下限，建立源和汇，对每个顶点，计算恰好满足流量下限时是输入多还是输出多，设d[x]是点x输入和输出差的绝对值，如果该点输出多，连接该点到汇的边，容量是d[x]，反之连接源到该点。最后检查源（汇）有关的边是否都满载，若满载则存在可行流。

我们可以这样理解，假设初始网络中满足每条边流量恰好为流量下限，但是这种情况下，网络不一定是平衡的，也就是有的点中“物质”会越来越多，有的点中“物质”会越来越少，我们就需要源/汇去供给/消耗不平衡的“物质”。

#include<iostream>    
#include<cmath>    
#include<cstring>    
#include<queue>    
#include<vector>    
#include<algorithm>    
#include<string.h>    
#include<cstdio>    
    
using namespace std;    
    
#define INF 100000010   
#define maxn 210  

struct Edge{      
    int u; int v;      
    int cap; int flow;      
    Edge(int u,int v,int c):u(u),v(v),cap(c),flow(0){}        
    Edge(){};      
};      
Edge edges[maxn*maxn];    
      
int ne;      
int head[maxn];      
int next[maxn*maxn];      
int n,m; 
int L[maxn*maxn]; 
int D[maxn]; 

void init(){      
    memset(head,-1,sizeof(head));   
	memset(D,sizeof(D));   
    ne=0;      
}      

int lv[maxn];      
bool bfs(int s,int t){      
    memset(lv,sizeof(lv)); lv[s]=0;      
    queue<int> que; que.push(s);       
    while(!que.empty()){      
        int cur=que.front(); que.pop();      
        for(int i=head[cur];i!=-1;i=next[i]){      
            Edge& e=edges[i];      
            if(lv[e.v]!=-1)continue;      
            if(e.flow<e.cap){      
                lv[e.v]=lv[cur]+1;      
                que.push(e.v);      
            }      
        }      
        if(lv[t]!=-1)return 1;      
    }      
    return 0;      
}      

int cur[maxn];
int dfs(int x,int a){      
    if(x==n+1||a==0)return a;      
    int re=0;      
    for(int& i=cur[x];i!=-1;i=next[i]){      
        Edge& e=edges[i];      
        int t;      
        if(lv[e.v]==(lv[x]+1)&& (t=dfs( e.v,min(a,e.cap-e.flow))) ){      
            edges[i].flow+=t;      
            edges[i^1].flow-=t;      
            re+=t;      
            a-=t;      
            if(a==0)break;      
        }      
    }      
    return re;      
}

int maxflow(int s,int t){      
    int flow=0;      
    while(bfs(s,t)){
        memcpy(cur,head,sizeof(head));      
        flow+=dfs(s,INF);  
    }      
    return flow;      
}

void addedge(int u,int c){      
    edges[ne]=Edge(u,v,c);        
    next[ne]=head[u];      
    head[u]=ne;      
    ne++;    
    edges[ne]=Edge(v,u,0);      
    next[ne]=head[v];      
    head[v]=ne;      
    ne++;      
}  
  
int main(){  
    int t;
    cin>>t;
	while(t--){  
    	cin>>n>>m;
        init();  
        for(int i=1;i<=m;i++){  
            int u,l,c;  
            scanf("%d%d%d%d",&u,&v,&l,&c);  
            addedge(u,c-l);  
            D[u]+=l;
            D[v]-=l;
            L[i]=l;  
        }
          
        for(int i=1;i<=n;i++){
            if(D[i]>0)  
                addedge(i,n+1,D[i]);  
            else  
                addedge(0,i,-D[i]);  
        }  
        
        maxflow(0,n+1);  
        bool ok=1;  
        for(int i=0;i<ne;i++){  
            if(edges[i].u==0){  
                if(edges[i].flow!=edges[i].cap)ok=0;  
            }  
        }  
        if(ok){  
            cout<<"YES"<<endl;  
            for(int i=1;i<=m;i++){  
                printf("%dn",edges[(i-1)*2].flow+L[i]);  
            }  
        }else{  
            cout<<"NO"<<endl;  
        }  
    }  
    return 0;  
}  

（编辑：李大同）

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