POJ3204+DInic+maxflow

Dinic+maxflow
题意：找这样一种边的个数，就是增加该边的容量，可以使得最大流变大

思路：求maxflow，再枚举流量为0的边，增加容量，看是否能找到增广路径。

/*
Dinic+maxflow
题意：找这样一种边的个数，就是增加该边的容量，可以使得最大流变大
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b)) 
const int maxn = 505;
const int maxm = 5005;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps = 1e-8;

struct Edge{
    int u,v,next,val;
    bool flag;
}edge[ maxm<<2 ];
int cnt,head[ maxn ];
int vis[ maxn ];
int lev[ maxn ];
int q[ maxn<<4 ];

void init(){
    cnt = 0;
    memset( head,-1,sizeof( head ) );
}
void addedge( int a,int b,int c ){
    edge[ cnt ].u = a;
    edge[ cnt ].v = b;
    edge[ cnt ].val = c;
    edge[ cnt ].next = head[ a ];
    if( cnt%2==0 ) edge[ cnt ].flag = true;
    else edge[ cnt ].flag = false;
    head[ a ] = cnt ++;
}

bool bfs( int n,int start,int end ){
    int head2 = 0,tail2 = 0;
    q[ tail2++ ] = start;
    memset( lev,-1,sizeof( lev ) );
    lev[ start ] = 0;
    while( head2<tail2 ){
        int u = q[ head2++ ];
        for( int i=head[u];i!=-1;i=edge[i].next ){
            int v = edge[i].v;
            if( edge[i].val>0&&lev[v]==-1 ){
                lev[v] = lev[u]+1;
                q[ tail2++ ] = v;
            }
        }
    }
    if( lev[ end ]==-1 ) return false;
    else return true;
}

int Dinic( int n,int start,int end ){
    int maxflow = 0;
    while( true ){
        if( bfs(n,start,end )==false ) break;
        int id = start;
        int tail = 0;
        while( true ){
            if( id==end ){
                int flow = inf;
                int flag = -1;
                for( int i=0;i<tail;i++ ){
                    if( edge[ q[i] ].val<flow ){
                        flow = edge[ q[i] ].val ;
                        flag = i;
                    }
                }
                for( int i=0;i<tail;i++ ){
                    edge[ q[i] ].val -= flow;
                    edge[ q[i]^1 ].val += flow;
                }
                if( flag!=-1 ){
                    maxflow += flow;
                    tail = flag;
                    id = edge[ q[flag] ].u;
                }
                else
                    return inf;
            }
            id = head[ id ];
            while( id!=-1 ){
                if( edge[id].val>0&&lev[edge[id].u]+1==lev[edge[id].v] ){
                    break;
                }
                id = edge[ id ].next;
            }
            if( id!=-1 ){
                q[ tail++ ] = id;
                id = edge[ id ].v;
            }
            else{
                if( tail==0 ) break;
                lev[ edge[q[tail-1]].v ] = -1;
                id = edge[ q[--tail] ].u;
            }
        }
    }
    return maxflow;
}                 

int main(){
    int n,m;
    while( scanf("%d%d",&n,&m)==2 ){
        init();
        int a,b,c;
        int start = 0;
        int end = n-1;
        for( int i=0;i<m;i++ ){
            scanf("%d%d%d",&a,&b,&c);
            addedge( a,b,c );
            addedge( b,a,0 );
        }
        Dinic( n,start,end );
        int ans = 0;
        for( int i=0;i<cnt;i++ ){
            if( edge[i].val==0&&edge[i].flag==true ){
                edge[i].val ++ ;
                if( bfs( n,start,end )==true ){
                    ans ++ ;
                }
                edge[i].val -- ;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}