# SGU 176. Flow construction

### Analyse :

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

（这个题。。。另一个不要想.#的方法是二分 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 n, m, s, t, ans;

void bfs(){
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 {
s = n; t = 1; C[n][1] = C[1][n] = 0; dinitz();
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(){
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