Brief description :

给定一张分层图，求一次阻塞流…

Analyse :

… 我还有东西需要确认。

/*
    Author: xiaodao
    Prog: ZOJ 2364 / SGU 212. Data Transmission
    Status: Labeled
    Last modify: GMT +8 Aug 22th 01:52
    Tags: Network_flow
*/


#include 
#include 
#include 
#include 

using namespace std;
const int INF = 0x7fffffff;
const int N = 1500, M = 300000 * 2;
struct edge{
    int v, c;
    void insert(int, int);
} E[M+1]; int edge_count;
vector adj[N+1], reverse_adj[N+1]; int D[N+1];
int n, m, l, s, t;


int _r(int x){
    return x ^ 1;
}

void edge::insert(int a, int b){
    v = a; c = b;
}

void add_edge(int x, int y, int c){
    adj[x].push_back(edge_count); E[edge_count++].insert(y, c);
}

void add_reverse_edge(int x, int y, int c){
    reverse_adj[x].push_back(edge_count); E[edge_count++].insert(y, c);
}





void Dinitz(){
    //bfs();
    //while (D[t]!=-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;

            //cout << u << endl;

            if (u == t){
                int handle = 1;
                for (int i=2;i<=top;i++)
                    if (E[stack[i]].c < E[stack[handle]].c)
                        handle = i;


                int delta = E[stack[handle]].c;

                for (int i=1;i<=top;i++){
                    E[stack[i]].c -= delta;
                    E[_r(stack[i])].c += delta;
                }

                for (int i=handle;i<=top;i++) //###
                    cur[E[stack[i]].v] = 0; // ###
                top = handle - 1;
                continue;
            }

            for (i=cur[u];i layer[N+1];
    long long excess[N+1];
    cin >> n >> m >> l;

    edge_count = 0;
    for (int i=1;i<=n;i++)
        adj[i].clear(), reverse_adj[i].clear();
    for (int i=1;i<=l;i++)
        layer[i].clear();


    for (int i=1;i<=n;i++){
        scanf("%d", &D[i]); layer[D[i]].push_back(i);
        if (D[i] == 1) s = i;
        else if (D[i] == l) t = i;
    }

    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        add_edge(x, y, c);
        add_reverse_edge(y, x, 0);
    }

    E[M].v = s; // ~







/* 我是贪心初始流。。。 */

/* 步骤一：灌水 */

    memset(excess, 0, sizeof(excess));
    //excess[s] = INF;
    excess[s] = ((long long)1 << 63 ) - 1;
    for (int i=1;i=2;i--){
        for (size_t j=0;j 0){
                for (size_t k=0;k= 0){
                            rev.c += excess[u]; arc.c -= excess[u];
                            excess[arc.v] += excess[u]; excess[u] = 0;
                            break;
                        }
                        else {
                            excess[u] -= arc.c; excess[arc.v] += arc.c;
                            rev.c += arc.c; arc.c = 0;
                        }
                    }
                }
            }
        }
    }
}

int main(){
    //int T; cin >> T;
    //for (int i=0;i
External link :
[ZJU][2364][Data Transmission]     Helanic Abyss

Andrew Stankevich’s Contest #3解题报告 by watashi
                                                												

													Posted by 
													xiaodao													
													Category: 													日常