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 head, tail;
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
                                                												

													Posted by 
													xiaodao													
													Category: 													日常