sgu 176 有源汇的上下界最小流（二分汇源的上界）（好题）

题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=176

题目大意：

　　给定一个网络，求1到n的一个最小流，有些边要求满载（满流），即有上下界容量限制的网络。

分析：

　　还是参考04年周源论文《一种简易的方法求解流量有上下界的网络中网络流问题》。

　　开始一直出不了sample，后来拿来了http://txhwind.diandian.com/post/2012-03-14/17480443代码来对（我前面那道题是参考他的写法）找了好久才发现对于n向1引一条边容量上界设置为二分的值，我把1写成了0……

　　注意1：所有边权之和作为二分的上限（当然这不是最快的，应该取 min( 1的所有出边权之和, n的所有入边权之和 ) + 1作为上限最合理）

　　注意2：二分答案后网络的表示g[][]会改变，但是最后输出答案要求用到相应的g[][]（残余网络），所以最后输出方案的时候必须把二分得到的最终的答案再次带入网络重新求一次最大流，这样得到的g[][]残余网络才是正确的，我是第一次碰见这种情况，值得借鉴，记牢。

　　注意3：因为每次要重新构图，所以g[][]必须每次初始化;

二分上界容量是一个很直观的方法，还有更高效的方法是：反向增广，我暂时不会。

附链接： http://www.shuizilong.com/house/archives/sgu-176-flow-construction/

代码：

sgu176

  1 /*17.06.12 13:24    yimao     176    .CPP    Accepted    218 ms    1179 kb*/
  2 // http://acm.sgu.ru/problem.php?contest=0&problem=176
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cmath>
  6 #include <iostream>
  7 #include <algorithm>
  8 #include <vector>
  9 using namespace std;
 10 
 11 #define mpair make_pair
 12 #define pii pair<int,int>
 13 #define MM(a,b) memset(a,b,sizeof(a));
 14 typedef long long lld;
 15 typedef unsigned long long u64;
 16 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
 17 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
 18 #define maxn 110
 19 const int inf= 2100000000;
 20 
 21 int n,m;
 22 int ST, ED;
 23 int g[maxn][maxn];
 24 int l[maxn][maxn], c[maxn][maxn];
 25 pii e[maxn*maxn];
 26 
 27 bool vis[maxn];
 28 int pre[maxn], que[maxn];
 29 bool bfs(){
 30     fill( vis, vis+2+n, 0 );
 31     int head= 0, tail= 0;
 32     que[tail++]= ST;
 33     vis[ST]= 0;
 34     while( head<tail ){
 35         int u= que[head++];
 36         for(int v=0;v<=ED;++v){
 37             if( g[u][v]>0 && !vis[v] ){
 38                 pre[v]= u;
 39                 if( v==ED ) return 1;
 40                 que[tail++]= v;
 41                 vis[v]= 1;
 42             }
 43         }
 44     }
 45     return 0;
 46 }
 47 int Edmond_karp(){
 48     int ret= 0;
 49     while( bfs() ){
 50         int t= inf;
 51         for(int i=ED;i!=ST;i=pre[i])
 52             up_min( t, g[pre[i]][i] );
 53         ret+= t;
 54         for(int i=ED;i!=ST;i=pre[i]){
 55             g[pre[i]][i]-= t;
 56             g[i][pre[i]]+= t;
 57         }
 58     }
 59     return ret;
 60 }
 61 
 62 bool ok(int mid){
 63     int sum= 0;
 64     MM( g, 0 ); /// each time we should rebuild the graph;
 65     c[n][1]= mid; /// n->1;
 66     for(int i=1;i<=n;++i){
 67         int t= 0;
 68         for(int j=1;j<=n;++j){
 69             t+= l[j][i]-l[i][j];
 70             g[i][j]= c[i][j]-l[i][j];
 71         }
 72         if( t>0 )
 73             sum+= g[ST][i] = t;
 74         else g[i][ED]= -t;
 75     }
 76     return Edmond_karp() >= sum;
 77 }
 78 
 79 int solve(int r){
 80     int lt=0, mid, ret= -1;
 81     while( lt<=r ){
 82         mid= (lt+r)>>1;
 83         if( ok(mid) ) r= mid-1, ret= mid;
 84         else lt= mid+1;
 85     }
 86     return ret;
 87 }
 88 
 89 int main()
 90 {
 91     //freopen("sgu176.in","r",stdin);
 92     while( cin>>n>>m ){
 93         ST= 0, ED= n+1;
 94         for(int i=0;i<=ED;++i)for(int j=0;j<=ED;++j)l[i][j]=c[i][j]=0;
 95 
 96         int limit= 0;
 97         for(int i=1;i<=m;++i){
 98             int u,v,w,t;
 99             scanf("%d%d%d%d", &u,&v,&w,&t);
100             e[i]= pii( u, v );
101             c[u][v]= w;
102             if( t ) l[u][v]= w;
103             limit+= w;
104         }
105 
106         int ret= solve( limit );
107         if( -1==ret ) puts("Impossible");
108         else{
109             printf("%d\n", ret);
110             ok( ret ); /// !!!
111             for(int i=1;i<=m;++i){
112                 int x= e[i].first, y= e[i].second;
113                 printf("%d%c", c[x][y]-g[x][y], i==m ? '\n' : ' ' );
114             }
115         }
116     }
117 }

一毛原创作品，转载请注明出处。