ZOJ 2314 Reactor Cooling（无源汇上下界网络流）-白红宇

ZOJ 2314 Reactor Cooling（无源汇上下界网络流）

阅读量：5162 次

发布时间：2019-06-13

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

题意：

给出每条边流量的上下界，问是否存在可行流，如果存在则输出。

思路：

先定义D（u）为顶点u发出的所有弧的流量下界与进入顶点u的所有弧的流量下界和之差（out【u】-in【u】）。

对于无源汇的网络流来说：

（1）新增两个顶点S（附加源点）和T（附加汇点）。

（2）对原网络中每个顶点u，计算出D（u），如果D（u）>0，则增加一条新弧<u,T>，这条弧的容量为D（u）；如果D（u）<0，则增加一条新弧<S,u>，这条弧的容量为-D（u）；如果D（u）=0，则不增加弧。

（3）原网络中的每条弧的容量更改为c-b（上界-下界）。

跑一遍最大流，如果满流，则存在可行流，每条边的实际流量=每条边的流量+该边流量下界。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
               10 #include
               11 #include
               
                 12 using namespace std; 13 typedef long long ll; 14 typedef pair
                
                  pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 50000 + 5; 17 18 int n, m; 19 20 int in[maxn]; 21 int out[maxn]; 22 int b[maxn]; 23 24 struct Edge 25 { 26 int from,to,cap,flow; 27 Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){} 28 }; 29 30 struct Dinic 31 { 32 int n,m,s,t; 33 vector
                 
                   edges; 34 vector
                  
                    G[maxn]; 35 bool vis[maxn]; 36 int cur[maxn]; 37 int d[maxn]; 38 39 void init(int n) 40 { 41 this->n=n; 42 for(int i=0;i

Q; 58 memset(vis,0,sizeof(vis)); 59 vis[s]=true; 60 d[s]=0; 61 Q.push(s); 62 while(!Q.empty()) 63 { 64 int x=Q.front(); Q.pop(); 65 for(int i=0;i

e.flow) 69 { 70 vis[e.to]=true; 71 d[e.to]=d[x]+1; 72 Q.push(e.to); 73 } 74 } 75 } 76 return vis[t]; 77 } 78 79 int DFS(int x,int a) 80 { 81 if(x==t || a==0) return a; 82 int flow=0, f; 83 for(int &i=cur[x];i

0) 87 { 88 e.flow +=f; 89 edges[G[x][i]^1].flow -=f; 90 flow +=f; 91 a -=f; 92 if(a==0) break; 93 } 94 } 95 return flow; 96 } 97 98 int Maxflow(int s,int t) 99 {100 this->s=s; this->t=t;101 int flow=0;102 while(BFS())103 {104 memset(cur,0,sizeof(cur));105 flow +=DFS(s,INF);106 }107 return flow;108 }109 110 void print(int num)111 {112 for(int i=0;i

转载于:https://www.cnblogs.com/zyb993963526/p/7256832.html

你可能感兴趣的文章

SAP HANA开发中常见问题- 基于SAP HANA平台的多团队产品研发