AC_Dream 1211 Reactor Cooling

/*

    題意：無源無彙，并且每條邊的容量有上下界限的網絡流問題！既然無源無彙，那麼素有的節點都應該滿足“入流==出流”！

         輸出每一條邊的流量，使得滿足上面的條件。（如果u->v有流量，那麼v->u就不會有流量）

    思路：如果增加了源點s和彙點t，對于u->v（下限為l， 上限為f） 将這一條邊拆成3條，s->v(容量為l)， u->v(容量為f-l)

     u->t(容量為l)這樣就變成了每一個點的流入或者流出的流量至少是b！然後從s->t走一遍最大流，如果所有的附件邊都已經

     滿載，則就是所有s->v的邊和u->t的邊（或者隻判斷其中一者就可以），那麼就存在答案！

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

#define INF 0x3f3f3f3f

#define N 205

#define M 500000

using namespace std;

struct EDGE{

    int v, cap, tot, nt, b;

    EDGE(){};

    EDGE(int v, int cap, int nt, int b) : v(v), cap(cap), nt(nt), b(b), tot(cap){}

};

EDGE edge[M];

int n, m;

int first[N];

int pre[N], d[N];

int sz;

int s, t;

int full, fout; 

void addEdge(int u, int v, int b, int cap){

    edge[sz] = (EDGE(v, cap, first[u],b));

    first[u] = sz++;

    edge[sz] = (EDGE(u, 0, first[v], 0));

    first[v] = sz++;

    edge[sz] = (EDGE(v, b, first[s], 0));

    first[s] = sz++;

    edge[sz] = (EDGE(s, 0, first[v], 0));

    edge[sz] = (EDGE(t, b, first[u], 0));

    full += b;

    edge[sz] = (EDGE(u, 0, first[t], 0));

    first[t] = sz++;

}

bool bfs(){

    queue<int>q;

    memset(d, 0, sizeof(d));

    d[s] = 1;

    q.push(s);

    while(!q.empty()){

        int u = q.front(); q.pop();

        for(int i = first[u]; ~i; i = edge[i].nt){

            int v = edge[i].v;

            if(!d[v] && edge[i].cap >0){

                d[v] = d[u] + 1;

                q.push(v);

            }

        }

    }

    if(d[t] == 0) return false;

    return true;

int dfs(int u, int totf){

    int ff;

    if( u == t) return totf;

    int flow = 0;

    for(int i = first[u]; ~i && totf > flow; i = edge[i].nt){

        int v = edge[i].v;

        int cap = edge[i].cap;

        //流入u節點的目前總的流量為totf，可以得到 u->v1, u->v2, u->v3....這些路徑上的最大流的和為flow+=f（u->vi）

        //f(u->vi)表示u節點沿着vi節點方向的路徑上的最大流；如果u->vi+1的容量為wi+1，那麼u->vi+1所允許流過的最大

        //的流量就是 min(totf - cost, wi+1)了！

        if(d[v] == d[u] + 1 && cap > 0 ){

            ff = dfs(v, min(totf - flow, cap));

            if(ff){

                edge[i].cap -= ff;

                edge[i^1].cap += ff;

                flow += ff;

            else

                d[v] = -1;//表示v這個點無法在繼續增廣下去了

    return flow;//傳回從u節點向外流出的最大流量！

bool Dinic(){

    while(bfs())

        fout += dfs(0, INF);//這一塊沒想到寫成while（dfs（））會逾時....

    if( fout != full) return false;

int main(){

        scanf("%d%d", &n, &m);

    memset(first, -1, sizeof(first));

    sz = 0;

    fout = full = 0;

    s = 0; t = n+1;

    int u, v, l, f;

    for(int i = 1; i <= m; ++i){

        scanf("%d%d%d%d", &u, &v, &l, &f);

        addEdge(u, v, l, f-l);

    if(!Dinic()){

        printf("NO\n");

        return 0;

    printf("YES\n");

        int j = (i-1)*6;

        printf("%d\n",  edge[j].tot - edge[j].cap + edge[j].b);//輸出這條邊實際流過的流量+下限

    return 0;

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/4006435.html，如需轉載請自行聯系原作者