# 某岛

… : "…アッカリ～ン . .. . " .. .
September 9, 2010

## ZOJ 2676. Network Wars

### Brief description :

/*
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{
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 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){
}

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;
Q[tail] = arc.v; V[arc.v].D = V[u].D + 1;
if (arc.v == t) return;
tail++;
}
}
}
}

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;
}

V[u].D = -1, top--;
}
else {
cur[u] = i + 1;
}
}
bfs();
}
}

void network_flow::init(){
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();
}
}