最大流算法 Dinic HDU 1532

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>

using namespace std;

#define V 205
#define E 205
#define INF 0x7ffffff

struct Edge
{
    int u, v, c, next;
} e[E<<2];

int n, m, s, t;
int d[V], head[V], cnt;

void adde(int u, int v, int c)
{
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].c = c;
    e[cnt].next = head[u];
    head[u] = cnt++;

    e[cnt].u = v;
    e[cnt].v = u;
    e[cnt].c = 0;
    e[cnt].next = head[v];
    head[v] = cnt++;
}

int bfs()
{
    memset(d, -1, (n+3)*sizeof(int));
    d[s] = 0;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i=head[u]; i!=-1; i=e[i].next)
        {
            int v = e[i].v;
            if(d[v]==-1 && e[i].c>0)
            {
                d[v] = d[u] + 1;
                Q.push(v);
            }
        }
    }
    return d[t] != -1;
}

int dfs(int x, int a)
{
    if(x==t || a==0) return a;
    int flow = 0, f;
    for(int i=head[x]; i!=-1 && flow<a; i=e[i].next)
    {
        int v = e[i].v;
        if(d[v]==d[x]+1 && e[i].c>0)
        {
            int t = min(e[i].c, a-flow);
            f = dfs(v, t);
            flow += f;
            e[i].c -= f;
            e[i^1].c += f;
        }
    }
    if(!flow)  d[x] = -2;
    return flow;
}

int dinic(int s, int t)
{
    int flow = 0, f;
    while(bfs())
    {
        while(f = dfs(s, INF))
            flow += f;
    }
    return flow;
}

int main()
{
    int u, v, c;
    while(~scanf("%d%d", &m, &n))
    {
        cnt = 0;
        memset(head, -1, (n + 3) * sizeof(int));
        s = 1;
        t = n;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d", &u, &v, &c);
            adde(u, v, c);
        }

        printf("%d\n", dinic(1, n));
    }
    return 0;
}