HDU4289Control 无向图拆点最大流

/*

**  无向图拆点，求最大流，最大流即为割点个数。

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const int maxn = 410;

const int maxm = 100100;

const int INF = 200000000;

struct node{

    int v,flow,next;

}edge[maxm];

int head[maxn],dis[maxn],aug[maxn];

int n,m,s,t,id;

void add_edge(int u,int v,int flow){

    edge[id].v = v;edge[id].flow = flow;edge[id].next = head[u];head[u] = id++;

    edge[id].v = u;edge[id].flow = 0   ;edge[id].next = head[v];head[v] = id++;

}

void init(){

    int cost,u,v;

    memset(head,-1,sizeof(head));id = 0;

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

        scanf("%d",&cost);

        add_edge(i,i+n,cost);

    }

    //v入，v+n出

    while( m-- ){

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

        add_edge(u+n,v,INF);

        add_edge(v+n,u,INF);

    }

    add_edge(0,s,INF);

    add_edge(t+n,n*2+1,INF);

    s = 0,t = n*2+1;

}

bool bfs(){

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

    queue<int>que;

    dis[s] = 0;

    que.push(s);

    while(!que.empty()){

        int u = que.front();

        que.pop();

        for(int id = head[u]; id != -1; id = edge[id].next){

            int v = edge[id].v;

            if( edge[id].flow > 0 && dis[v] == -1){

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

                que.push(v);

            }

        }

    }

    return dis[t] != -1;

}

int min(int x,int y){

    return x < y ? x : y;

}

int dinic(int u,int flow){

    if(u == t || flow == 0)return flow;

    int tmp = flow;

    for(int id = head[u]; id != -1; id = edge[id].next){

        int v = edge[id].v;

        if( edge[id].flow > 0 && dis[v] == dis[u] + 1){

            int tt = dinic(v,min(tmp,edge[id].flow));

            tmp -= tt;

            edge[id].flow -= tt;

            edge[id^1].flow += tt;

            if(tmp == 0) break;

        }

    }

    return flow - tmp;

}

int main(){

    //freopen("in.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){

        scanf("%d%d",&s,&t);

        init();

       // cout << id << endl;

        int max_flow = 0;

        while(bfs())

            max_flow += dinic(s,INF);

        printf("%d\n",max_flow);

    }

    return 0;

}