sgu176 Flow Construction【有源汇有上下界最小流】

　　同样是模板题。

　　首先将有源汇转换为无源汇，假设原来的源汇为st，我们加入的源汇为ST，那么我们应该从t到s连一条流量为+∞的边，使原来的st满足收支平衡，退化为普通节点。

　　分离必要边和其他边，从S到T跑最大流，所有与源或者汇相连的边都流满则证明有解。

　　去掉t到s容量为+∞的边，去掉必要边，从t到s跑最大流。

　　把得到的答案相减即可。

　　如果我们得到的答案是负的，那么说明它内部t到s连成了环，那么我们加上S到s容量为-ans的边，跑S到t的最大流，这样所有的边的流量应该就是0，再加上流量下界即为答案。

 #include <bits/stdc++.h>

 #define rep(i, a, b) for (int i = a; i <= b; i++)

 #define drep(i, a, b) for (int i = a; i >= b; i--)

 #define REP(i, a, b) for (int i = a; i < b; i++)

 #define mp make_pair

 #define pb push_back

 #define clr(x) memset(x, 0, sizeof(x))

 #define xx first

 #define yy second

 using namespace std;

 typedef long long i64;

 typedef pair<int, int> pii;

 const int inf = ~0U >> ;

 const i64 INF = ~0ULL >> ;

 //******************************

 const int maxn = , maxm = ;

 struct Ed {

     int u, v, nx, c; Ed() {}

     Ed(int _u, int _v, int _nx, int _c) :

         u(_u), v(_v), nx(_nx), c(_c) {}

 } E[maxm << ];

 int G[maxn], edtot = ;

 void addedge(int u, int v, int c) {

     E[++edtot] = Ed(u, v, G[u], c);

     G[u] = edtot;

     E[++edtot] = Ed(v, u, G[v], );

     G[v] = edtot;

 }

 int level[maxn], S, T;

 bool bfs(int s, int t) {

     static int que[maxn]; int qh(), qt();

     clr(level); level[que[++qt] = s] = ;

     while (qh != qt) {

         int x = que[++qh]; if (qh == maxn - ) qh = ;

         for (int i = G[x]; i; i = E[i].nx) if (E[i].c && !level[E[i].v]) {

             level[que[++qt] = E[i].v] = level[x] + ;

             if (qt == maxn - ) qt = ;

         }

     }

     return !!level[t];

 }

 int dfs(int u, int rm, int t) {

     if (u == t) return rm;

     int rm1 = rm;

     for (int i = G[u]; i; i = E[i].nx) {

         if (E[i].c && level[E[i].v] == level[u] + ) {

             int flow = dfs(E[i].v, min(E[i].c, rm), t);

             E[i].c -= flow, E[i ^ ].c += flow;

             if ((rm -= flow) == ) break;

         }

     }

     if (rm1 == rm) level[u] = ;

     return rm1 - rm;

 }

 int l[maxm], in[maxn];

 int main() {

     int n, m;

     scanf("%d%d", &n, &m);

     rep(i, , m) {

         int x, y, a, b; scanf("%d%d%d%d", &x, &y, &a, &b);

         l[i] = a * b;

         if (b) in[y] += a, in[x] -= a;

         addedge(x, y, a - a * b);

     }

     S = n + , T = n + ;

     int sum();

     rep(i, , n) {

         if (in[i] > ) sum += in[i];

         if (in[i] > ) addedge(S, i, in[i]);

         else addedge(i, T, -in[i]);

     }

     addedge(n, , 0x3f3f3f3f);

     while (bfs(S, T)) sum -= dfs(S, 0x3f3f3f3f, T);

     if (sum) { puts("Impossible"); return ; }

     int ans = E[edtot].c;

     E[edtot].c = E[edtot ^ ].c = ;

     int tmp();

     while (bfs(n, )) tmp += dfs(n, 0x3f3f3f3f, );

     ans -= tmp;

     if (ans < ) {

         addedge(S, , -ans);

         while (bfs(S, n)) dfs(S, 0x3f3f3f3f, n);

         ans = ;

     }

     printf("%d\n", ans);

     rep(i, , m) {

         printf(i ==  ? "%d" : " %d", E[(i << ) ^ ].c + l[i]);

     }

     puts("");

     return ;

 }