### Brief description :

給定一個流網路，選取一個包含割的邊集E，使得邊權的平均值最小。

```
/*
Author : xiaodao
Problem : ZOJ 2676. Network Wars
Status : Accepted
Last Modify : GMT +8. Sept 9th 14:48.
Tags : 0/1分數規劃，最小割
*/
#include
```
#include
#include
#include
#include
using namespace std;
const double EPS = 1e-6, INF = 1e9;
const int N = 500, M = 2000;
struct edge{
int v, c; double cc; bool used;
void insert(int, int);
};
struct node{
vector adj;
int D;
};
struct network_flow{
node V[N+1]; edge E[M+1];
int edge_count; double max_flow, negative_edge;
int n, m, s, t;
void init();
void print();
void rebuild(double);
void add_edge(int, int, int);
void bfs();
void Dinitz();
};
inline int _r(int x){
return x ^ 1;
}
void edge::insert(int a, int b){
v = a; c = b; used = false;
};
void network_flow::add_edge(int x, int y, int z){
V[x].adj.push_back(edge_count); E[edge_count++].insert(y, z);
}
void network_flow::bfs(){
int Q[N+1] = {s}, head = 0, tail = 1;
for (int i=1;i<=n;i++) V[i].D = -1;
V[s].D = 0;
int u;
while (head0){
Q[tail] = arc.v; V[arc.v].D = V[u].D + 1;
if (arc.v == t) return;
tail++;
}
}
head++;
}
}
void network_flow::Dinitz(){
max_flow = 0;
bfs();
while (V[t].D!=-1){
int stack[n+1], cur[n+1], top = 0;
memset(cur, 0, sizeof(cur));
stack[0] = M;
int u; size_t i;
while (top!=-1){
u = E[stack[top]].v;
if (u == t){
double delta = INF; int handle;
for (int i=1;i<=top;i++){
edge &arc = E[stack[i]];
if (arc.cc < delta){
delta = arc.cc;
handle = i;
}
}
max_flow += delta;
for (int i=1;i<=top;i++){
E[stack[i]].cc -= delta;
E[_r(stack[i])].cc += delta;
}
//for (int i=handle;i<=top;i++){
// cur[stack[i]] = 0;
//} // ?
top = handle-1;
continue;
}
for (i=cur[u];i0) break;
}
if (i == V[u].adj.size()){
V[u].D = -1, top--;
}
else {
cur[u] = i + 1;
stack[++top] = V[u].adj[i];
}
}
bfs();
}
}
void network_flow::init(){
for (int i=1;i<=n;i++) V[i].adj.clear();
edge_count = 0; s = 1; t = n;
E[M].v = s;
int x, y, z;
for (int i=0;i=0) != (V[E[2*i+1].v].D>=0) )
E[2*i].used = true;
int count = 0;
for (int i=0;i 0) l = m;
else r = m;
}
G.print();
}
}