hdu 4289 最小割，分拆点为边

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2609

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <cstring>

#include <queue>

#include <vector>

#define maxn 450

#define maxe 100000

using namespace std;

const int INF = 0x3f3f3f;

struct Edge{

    int from,to,cap,flow;

    int next;

};

struct Dinic{

    int s,t;

    int head[maxn];

    int cur[maxn];

    Edge edges[maxe];

    int d[maxn];

    bool vis[maxn];

    int cnt;

       void init(){

         memset(head,-,sizeof(head));

         cnt = ;

    }

    void addedge(int from,int to,int cap){

        edges[cnt].from = from; edges[cnt].to = to;   edges[cnt].cap = cap;

        edges[cnt].flow =    ; edges[cnt].next = head[from];  head[from] = cnt++;

        edges[cnt].from = to  ; edges[cnt].to = from; edges[cnt].cap = ;

        edges[cnt].flow =    ; edges[cnt].next = head[to];  head[to] = cnt++;

    }

    bool bfs(){

        memset(vis,,sizeof(vis));

        queue<int> Q;

        Q.push(s);

        vis[s] = true;

        d[s] = ;

        while(!Q.empty()){

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

            for(int i=head[u];i!=-;i=edges[i].next){

                Edge& e = edges[i];

                if(!vis[e.to] && e.cap>e.flow){

                    vis[e.to] = true;

                    d[e.to] = d[e.from] + ;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int dfs(int u,int res){

        if( u == t ||  res == )   return res;

        int flow = ,f;

        for(int& i=cur[u];i!=-;i=edges[i].next){   //还不是很理解到cur[]的作用；

            Edge& e = edges[i];

            if(d[e.to] == d[e.from] +  && (f = dfs(e.to,min(res,e.cap-e.flow)))>){

                e.flow += f;

                edges[i^].flow -= f;

                flow += f;

                res -= f;

                if(res == ) break;

            }

        }

        return flow;

    }

    int Maxflow(int S,int T){

        s = S; t = T;

        int flow = ;

        while(bfs()){

            for(int i=s;i<=t;i++)  cur[i] = head[i];

            flow += dfs(s,INF);

        }

        return flow;

    }

}solver;

int main()

{

    //if(freopen("input.txt","r",stdin)== NULL)  {printf("Error\n"); exit(0);}

    int N,M,S,T;

    while(scanf("%d%d",&N,&M) == ){

        scanf("%d%d",&S,&T);

        solver.init();

        int s,t;

        s = ;  t = *N + ;

        solver.addedge(s,S,INF);

        solver.addedge(T+N,t,INF);  //

        for(int i=;i<=N;i++){

            int cost;

            scanf("%d",&cost);

            solver.addedge(i,i+N,cost);

        }

        for(int i=;i<=M;i++){

            int a,b;

            scanf("%d %d",&a,&b);

            solver.addedge(b+N,a,INF);

            solver.addedge(a+N,b,INF);

        }

        printf("%d\n",solver.Maxflow(s,t));

    }

}