# ZOJ 2314. Reactor Cooling

### Brief description :

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314

/*
ID: xiaodao
PROG: ZOJ 2314. Reactor Cooling
TAGS: Network_Flow
*/

#include
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 302, M = 1000000;
struct rec{
int v, p, k;
// Vertex, Parient ,key
};
int x[M], y[M], l[M], r; // Edge ..
int C[N][N], F[N][N]; // Capacity, Flow..
bool V[N]; rec Q[N]; // Visited, Queue..
int n, m, ans;

bool find_path(){
memset(V, false, sizeof(V));
Q[0].v = 0; Q[0].k = INF; V[0] = true;
head = 0; tail = 1;
int u, v;

while (head> n >> m; n++;
for (int i=0;i> T;
for (int i=0;i
/*
ID: xiaodao
PROG: ZOJ 2314. Reactor Cooling
TAGS: Network_Flow
*/

#include
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 302, M = 1000000;
int x[M], y[M], l[M], r; // Edge ..
int C[N][N], F[N][N]; // Capacity, Flow..
int H[N], E[N]; // .Height, Excess ...
int n, m, sum;
bool changed;

void push(int u, int v, int delta){
F[u][v] += delta; F[v][u] -= delta;
E[u] -= delta; E[v] += delta;
}

void relabel(int u){
H[u] = INF;
for (int v=0;v<=n;v++){
if (u!=v && F[u][v] < C[u][v])
H[u] = min(H[u], H[v]+1);
}
}

void discharge(int u){
if (E[u]==0){
changed = false;
return;
}

changed = true;
for (int v=0;v<=n;v++){
if (u == v) continue;
if (H[u] > H[v] && F[u][v] < C[u][v]){
push(u, v, min(E[u], C[u][v] - F[u][v]));
if (E[u]==0) {changed = false; return;}
}
}
relabel(u);
}

void relabel_to_front(){
//Relabel-to-front algorithm, ie. using FIFO heuristic

//1.Send as much flow from s as possible.
memset(E, 0, sizeof(E));
memset(H, 0, sizeof(H));
E[0] = INF; H[0] = n+1;

for (int i=1;i<=n;i++){
if (C[0][i] > 0) {
push(0, i, C[0][i]);
if (i!=n) H[i] = 1;
}
}

//2.Build a list of all nodes except s and t.
list L;
for (int i=1;i::iterator it=L.begin();
while (it!=L.end()){
//1.Discharge the current node.
discharge(*it);
//2.If the height of the current node changed:
if (changed){
// Move the current node to the front of the list ...
L.push_front(*it); L.erase(it);
// .. And restart the traversal from the front of the list.
it = L.begin();
}
else
it++;
}
}

void init(){
memset(C, 0, sizeof(C));
memset(F, 0, sizeof(F));
cin >> n >> m; n++;
sum = 0;
for (int i=0;i> T;
for (int i=0;i