ZOJ 2314 Reactor Cooling

ZOJ 2314 Reactor Cooling

很裸地无源汇的可行流，我看了看论文但是不是很明白他的工作原理，虽然A了，但是心里没底。。

纯粹留下代码，方便以后用。。

#include<string>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 210;

class Arc{
public:
    int to,w;
    int cap,low;
    Arc *next,*anti;
    Arc *ass( int tt,int cc,int ll,int ww,Arc* &b ){
        to=tt;cap=cc;low=ll;next=b;b=this;
        w = ww;
        return this;
    }
} a[ maxn*maxn ],*biao[ maxn ];

int countt,d[ maxn ],S,T,N,M;
int inlbsum[ maxn ];
int outlbsum[ maxn ];

void add( int from,int to,int lb,int cap ){

    outlbsum[from] += lb;
    inlbsum[to] += lb;
    Arc *p1 = a[ countt++ ].ass(to,cap,lb,cap-lb,biao[from]);
    Arc *p2 = a[ countt++ ].ass(from,0,0,0,biao[to]);
    p1->anti = p2;
    p2->anti = p1;
}

int bfs( void ){
    queue<int> q;
    fill( d+1,d+1+N+2,-1);
    d[S] = 0;
    q.push( S );
    while( !q.empty() ){
        int u = q.front();q.pop();
        for( Arc *p = biao[u]; p != NULL; p = p->next ){
            if( d[ p->to ] == -1 && p->w > 0 )
                d[ p->to ] = d[u]+1,q.push( p->to );
        }
    }
    return d[T]!=-1;
}

int dinic( int u,int sum ){
    int f,o;
    if( u == T ) return sum;
    o = sum;
    for( Arc *p = biao[u]; p != NULL; p = p->next )
        if( d[p->to] == d[u]+1 && p->w > 0 ){
            f = dinic(p->to,min(p->w,sum));
            p->w -= f;
            p->anti->w += f;
            sum -= f;
        }
    return o-sum;
}

bool full( void ){
    for( Arc *p = biao[S]; p != NULL; p = p->next )
        if( p->w ) return false;
    return true;
}

int main(void){
    int i,j,cases;
    int from,to,lb,cap;
    scanf("%d",&cases);
    while( cases-- ){
        scanf("%d%d",&N,&M);
        S = N+1;
        T = N+2;
        for( i = 1; i <= N+2; i++ )
            biao[i] = NULL,inlbsum[i]=outlbsum[i]=0;
        countt = 0;
        for( i = 0; i < M; i++ ){
            scanf("%d%d%d%d",&from,&to,&lb,&cap);
            add(from,to,lb,cap);
        }

        for( i = 1; i <= N; i++ ){
            if( inlbsum[i] > outlbsum[i] )
                add( S,i,0,inlbsum[i]-outlbsum[i] );
            if( outlbsum[i] > inlbsum[i] )
                add( i,T,0,outlbsum[i]-inlbsum[i] );
        }

        int total = 0;
        while( bfs() )
            total += dinic(S,2100000000);

        if( full() ) {
            printf("YES\n");
        }
        else{
            printf("NO\n");
            if( cases ) puts("");
            continue;
        }

        for( i = 0; i < 2*M; i += 2 )
            printf("%d\n",a[i].cap - a[i].w);
        if( cases ) cout<< endl;
    }
    return 0;
}