acdream 1211 Reactor Cooling 【边界网络流量 + 输出流量】-白红宇

acdream 1211 Reactor Cooling 【边界网络流量 + 输出流量】

阅读量：5264 次

发布时间：2019-06-14

本文共 2164 字，大约阅读时间需要 7 分钟。

称号：

分类：无汇的有上下界网络流。

题意：

给n个点。及m根pipe，每根pipe用来流躺液体的。单向的。每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体。里面流躺物质。

而且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)。同一时候最小不能低于Li。

比如：

46(4个点，6个pipe)

12 1 3 (1->2上界为3，下界为1)

23 1 3

3 4 1 3

4 1 1 3

1 3 1 3

4 2 1 3

可行流：

再如：全部pipe的上界为2下界为1的话，就不能得到一种可行流。

题解：

上界用ci表示，下界用bi表示。

下界是必须流满的，那么对于每一条边，去掉下界后，其自由流为ci– bi。

主要思想：每个点流进来的流=流出去的流

对于每个点i，令

Mi= sum(i点全部流进来的下界流)– sum(i点全部流出去的下界流)

假设Mi大于0，代表此点必须还要流出去Mi的自由流，那么我们从源点连一条Mi的边到该点。

假设Mi小于0，代表此点必须还要流进来Mi的自由流。那么我们从该点连一条Mi的边到汇点。

假设求S->T的最大流，看是否满流(S的相邻边都流满)。

满流则有解，否则无解。

AC代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define Del(a,b) memset(a,b,sizeof(a))using namespace std;const int inf = 0x3f3f3f3f;const int N = 250;struct Node{ int from,to,cap,flow;};vector
             
               v[N];vector
              
                e;int vis[N]; //构建层次图int cur[N];void add_Node(int from,int to,int cap){ e.push_back((Node){from,to,cap,0}); e.push_back((Node){to,from,0,0}); int tmp=e.size(); v[from].push_back(tmp-2); v[to].push_back(tmp-1);}bool bfs(int s,int t){ Del(vis,-1); queue
               
                 q; q.push(s); vis[s] = 0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i
                
                 tmp.flow) //第二个条件保证 { vis[tmp.to]=vis[x]+1; q.push(tmp.to); } } } if(vis[t]>0) return true; return false;}int dfs(int o,int f,int t){ if(o==t || f==0) //优化 return f; int a = 0,ans=0; for(int &i=cur[o];i
                 
                  0) { tmp.flow+=a; e[v[o][i]^1].flow-=a; //存图方式 ans+=a; f-=a; if(f==0) //注意优化 break; } } return ans; //优化}int dinci(int s,int t){ int ans=0; while(bfs(s,t)) { Del(cur,0); int tm=dfs(s,inf,t); ans+=tm; } return ans;}void MP_clear(int n){ for(int i=0;i<=n;i++) v[i].clear(); e.clear();}int come[N],to[N];int flow[N][N];struct Node1{ int x,y;}num[N*N];int main(){ int n,m; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); Del(come,0); Del(to,0); Del(flow,0); int s=0,t = n+1; for(int i=0;i
                  
                   0) add_Node(i,t,tmp); } count = -count; int ans = dinci(s,t); if(ans != count) puts("NO"); else { puts("YES"); for(int i=1;i<=n;i++) { for(int j=0;j

转载于:https://www.cnblogs.com/yxwkf/p/4856041.html

你可能感兴趣的文章