Brief description :

有上下界网络的最小流。

Analyse :

因为是一个子步骤，大家都推荐先做这个题，咳咳。。。
… 发现求最小流只是需要把源点和汇点交换反过来推回去就行了，但是可能会产生一个BUG。。会出现负的最小流。#（分析其产生的原因是源点和汇点会破坏了流守恒，当然源点破坏了没关系，可是我们不是交换过来了嘛。#）

新建源点 0，在 0 和 1 之间连一条流量为 -（steady_flow – max_flow）的边，然后再做一次 Dinitz 把负流推成了0.。。
（这个题。。。另一个不要想.#的方法是二分 C[n][1] 的流量 …）

/*
    Author: xiaodao
    Prob: SGU 176. Flow construction
    Date: GMT +8 Aug.19th 04:41
    Status: Accepted
    Tags: Network-Flow, Dinitz
*/

#include 
#include 
#include 
using namespace std;
const int INF = 0x7fffffff;
const int N = 102, M = N*N/2;
int C[N][N], D[N];
int x[M], y[M], l[M], r;
int necessary_flow, steady_flow, max_flow;
int n, m, s, t, ans;




void bfs(){
    int Q[N], head, tail;
    memset(D, -1, sizeof(D));
    head = 0; tail = 1; Q[0] = s; D[s] = 0;

    int u, v;
    while (headn) D[u] = -1, top--;
            else {
                cur[u] = v + 1;
                stack[++top] = v;
            }
        }
        bfs();
    }
}

void recover(){
    s = 0; t = n; C[s][1] = -ans; dinitz();
    ans = 0;
}

void init(){
    memset(C, 0, sizeof(C));
    n++; necessary_flow = 0;
    for (int i=0;i> n >> m){
        init(); s = 0; t = n; dinitz();
        if (max_flow!=necessary_flow) printf("Impossible\n");
        else {
            steady_flow = C[1][--n];
            s = n; t = 1; C[n][1] = C[1][n] = 0; dinitz();
            ans = steady_flow - max_flow;
            if (ans < 0) recover(); // T T
            cout << ans << endl;
            for (int i=0;i
/*
    Author: xiaodao    
    Prob: SGU 176. Flow construction 
    Date: GMT +8 Aug.19th 04:19
    Status: Accepted        
    Tags: Network-Flow, Dinitz
*/

#include 
#include 
#include 
using namespace std;
const int INF = 0x7fffffff;
const int N = 102, M = N*N/2;
int C[N][N], F[N][N], D[N];
int x[M], y[M], l[M], r;
int necessary_flow, max_flow;
int n, m, s, t; int limit;




void bfs(){
    int Q[N], head, tail;
    memset(D, -1, sizeof(D));
    head = 0; tail = 1; Q[0] = s; D[s] = 0;

    int u, v;
    while (headn) D[u] = -1, top--;
            else {
                cur[u] = v + 1;
                stack[++top] = v;
            }
        }
        bfs();
    }
}


int binary_search(int l, int r){
    int m;
    while (l < r){
        m = (l + r) / 2;
        C[n-1][1] = m; dinitz();
        if (max_flow==necessary_flow) r = m;
        else l = m + 1;
    }
    if (l == m + 1) C[n-1][1] = l, dinitz(); // T T.
    return l;
}


void init(){
    memset(C, 0, sizeof(C)); limit = 0;
    necessary_flow = 0; n++;
    for (int i=0;i> n >> m){
        init(); s = 0; t = n; dinitz();
        if (max_flow!=necessary_flow) printf("Impossible\n");
        else {
            cout << binary_search(0 , limit) << endl;
            for (int i=0;i
External link :

http://acm.sgu.ru/problem.php?contest=0&problem=176

http://hi.baidu.com/hefeizhousiyuan/blog/item/f4775339adc438fa3b87ce16.html
                                                												

													Posted by 
													xiaodao													
													Category: 													日常