[上下界最小流] SGU 176. Flow construction

176. Flow construction

题意：

从1到n的一个网络，每个边有上下界，求最小流。

思路：

属于有源汇上下界的最小流问题，总结下。

1. 原网络每条边的容量为 CMax−CMin ，同时记录每个点的下界流量，流入为正，流出为负，记为 flow[i] 。
2. 建立每个点和 ss 及 tt 之间的边，若 flow[i]>0 ，连接 ss 和 i ,容量为 flow[i] ，若 flow[i]<0 ，连接 i 和 tt ，容量为 −flow[i] ，记录 ss 的流出和 tt 的流入，用于判断无解。
3. 跑一遍 ss 和 tt 的最大流，记流量为 maxflow 。
4. 加上 t 到 s 的边，容量为 inf ，记为 edgts 。
5. 跑一遍 ss 和 tt 的最大流，累加在 maxflow 上。
6. 当 maxflow==flow[ss] and flow[ss]==flow[tt] 时有解。
7. s到t的最小流为 edgts 的流量，各边的流量为下界+对应边的流量。

#include<bits/stdc++.h>
using namespace std;
const int N = 205;
const int M = 205*205;
const int inf = ~0u>>2;
struct eg{
int u, v, cap; //源点汇点流量
    eg(){}
    eg(int a, int b, int c){ u = a, v = b, cap = c; }
}edg[M]; //边数开大
int fir[N], nex[M], ecnt, s, t;
int id[M];
void add(int a, int b, int c, int i = 0){
    id[i] = ecnt;
    edg[ecnt] = eg(a, b, c);
    nex[ecnt] = fir[a], fir[a] = ecnt++;
    edg[ecnt] = eg(b, a, 0);
    nex[ecnt] = fir[b], fir[b] = ecnt++;
}
int lev[N], q[N*4], top, tail;
bool Bfs(int s, int t){
    memset(lev, -1, sizeof(lev));
    top = tail = 0;
    lev[s] = 0; q[tail++] = s;
while( top < tail  ){
int u = q[top++];
if( u == t ) return 1;
for(int k = fir[u]; k != -1; k = nex[k]){
int v = edg[k].v;
if( edg[k].cap && lev[v] == -1){
                lev[v] = lev[u] + 1;
q[tail++] = v;
            }
        }
    }
return 0;
}
int Dfs(int s, int t, int low){
if( s == t ) return low;
int a = 0, res = 0;
for(int k = fir[s]; k != -1; k = nex[k]){
int v = edg[k].v;
if(edg[k].cap && lev[v] == lev[s] +1 ){
            a = Dfs(v, t, min(low - res, edg[k].cap) );
            edg[k].cap -= a;
            edg[k^1].cap += a;
            res += a;
if(res == low) return res;
        }
    }
if(res == 0) lev[s] = -1;
return res;
}
int Dinic(int s, int t){
int res = 0, minflow;
while( Bfs(s, t) ){
while( minflow = Dfs(s, t, inf) ) res += minflow;
    }
return res;
}
int flow[N];
int ans[M][3];
int main(){
    ecnt = 0; memset(fir, -1, sizeof(fir));
    memset(flow, 0, sizeof(flow));
    memset(ans, 0, sizeof(ans));
    memset(id, 0, sizeof(id));
int n, m;
    scanf("%d%d", &n, &m);
for(int u, v, z, c, i = 1; i <= m; ++i){
        scanf("%d%d%d%d", &u, &v, &z, &c);
if(c) flow[u] -= z, flow[v] += z;
else add(u, v, z, i);
        ans[i][0] = u, ans[i][1] = v, ans[i][2] = c? z : 0;
    }
s = 1, t = n;
int ss = 0, tt = n+1;
for(int i = 1; i <= n; ++i){
if(flow[i] > 0) add(ss, i, flow[i]), flow[ss] += flow[i];
else if(flow[i] < 0) add(i, tt, -flow[i]), flow[tt] += -flow[i];
    }
int maxflow = Dinic(ss, tt);
    add(t, s, inf);
    maxflow += Dinic(ss, tt);
if(maxflow == flow[ss] && flow[ss] == flow[tt]){
for(int i = 1; i <= m; ++i){
if(ans[i][2] == 0) ans[i][2] = edg[id[i]^1].cap;
        }
printf("%d\n", edg[ecnt-1].cap);
for(int i = 1; i <= m; ++i){
printf("%d ", ans[i][2]);
        }
        puts("");
    }
else puts("Impossible");
return 0;
}