HDU 1532 --&&-- POJ1273 dinic 算法

学长的代码
#include<stdio.h>

#include<string.h>

#include<queue>

#include<algorithm>

using namespace std;

const int MAXN = 1005;

const int oo = 1e9+7;

struct Edge

{

    int v, flow, next;

}edge[MAXN];

int Head[MAXN], cnt;

int Layer[MAXN];

void InIt()

{

    cnt = 0;

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

}

void AddEdge(int u, int v, int flow)

{

    edge[cnt].v = v;

    edge[cnt].flow = flow;

    edge[cnt].next = Head[u];

    Head[u] = cnt++;

    swap(u, v);

    edge[cnt].v = v;

    edge[cnt].flow = 0;

    edge[cnt].next = Head[u];

    Head[u] = cnt++;

}

bool BFS(int start, int End)

{

    memset(Layer, 0, sizeof(Layer));

    queue<int> Q;

    Q.push(start);

    Layer[start] = 1;

    while(Q.size())

    {

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

        if(u == End)return true;

        for(int j=Head[u]; j!=-1; j=edge[j].next)

        {

            int v = edge[j].v;

            if(Layer[v] == 0 && edge[j].flow)

            {

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

                Q.push(v);

            }

        }

    }

    return false;

}

int DFS(int u, int MaxFlow, int End)

{

    if(u == End)return MaxFlow;

    int uflow = 0;

    for(int j=Head[u]; j!=-1; j=edge[j].next)

    {

        int v = edge[j].v;

        if(Layer[v]==Layer[u]+1 && edge[j].flow)

        {

            int flow = min(edge[j].flow, MaxFlow-uflow);

            flow = DFS(v, flow, End);

            edge[j].flow -= flow;

            edge[j^1].flow += flow;

            uflow += flow;

            if(uflow == MaxFlow)

                break;

        }

    }

    if(uflow == 0)

        Layer[u] = 0;

    return uflow;

}

int Dinic(int start, int End)

{

    int MaxFlow = 0;

    while(BFS(start, End) == true)

        MaxFlow += DFS(start, oo, End);

    return MaxFlow;

}

int main()

{

    int N, M;

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

    {

        int u, v, flow;

        InIt();

        while(M--)

        {

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

            AddEdge(u, v, flow);

        }

        printf("%d\n", Dinic(1, N));

    }

    return 0;

}
巴特西

HDU 1532 --&&-- POJ1273 dinic 算法

最新文章

热门文章
