poj1273

赤裸裸的最大流

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

#define maxn 205

#define maxm 205

#define inf (1 << 30)

struct Edge

{

    int next, v, f;

} edge[maxm * ];

int n, m;

int head[maxn];

int q[maxn];

bool vis[maxn];

int cur[maxn];

int dep[maxn];

int ncount;

int path[maxn];

void addedge(int a, int b, int f)

{

    edge[ncount].v = b;

    edge[ncount].f = f;

    edge[ncount].next = head[a];

    head[a] = ncount++;

}

void input()

{

    ncount = ;

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

    for (int i = ; i < m; i++)

    {

        int a, b, f;

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

        a--;

        b--;

        addedge(a, b, f);

        addedge(b, a, );

    }

}

void bfs(int s, int t)

{

    memset(vis, , sizeof(vis));

    memset(dep, -, sizeof(dep));

    int front = , rear = ;

    q[rear++] = s;

    vis[s] = true;

    dep[s] = ;

    while (front != rear && !vis[t])

    {

        int u = q[front++];

        for (int i = head[u]; ~i; i = edge[i].next)

        {

            int v = edge[i].v;

            if (!vis[v] && edge[i].f > )

            {

                q[rear++] = v;

                vis[v] = true;

                dep[v] = dep[u] + ;

            }

        }

    }

}

int dinic(int s, int t)

{

    int ret = ;

    while (true)

    {

        bfs(s, t);

        if (dep[t] == -)

            break;

        int path_n = ;

        int x = s;

        memcpy(cur, head, sizeof(cur));

        while (true)

        {

            if (x == t)

            {

                int mink = -, delta = inf;

                for (int i = ; i < path_n; ++i)

                {

                    if (edge[path[i]].f < delta)

                    {

                        delta = edge[path[i]].f;

                        mink = i;

                    }

                }

                for (int i = ; i < path_n; ++i)

                {

                    edge[path[i]].f -= delta;

                    edge[path[i] ^ ].f += delta;

                }

                ret += delta;

                path_n = mink;

                if (path_n)

                    x = edge[path[path_n - ]].v;

                else

                    x = s;

            }

            int e;

            for (e = cur[x]; ~e; e = edge[e].next)

            {

                if (edge[e].f == )

                    continue;

                int y = edge[e].v;

                if (dep[x] +  == dep[y])

                    break;

            }

            cur[x] = e;

            if (~e)

            {

                path[path_n++] = e;

                x = edge[e].v;

            }

            else

            {

                if (path_n == )

                    break;

                dep[x] = -;

                --path_n;

                if (path_n)

                    x = edge[path[path_n - ]].v;

                else

                    x = s;

            }

        }

    }

    return ret;

}

int main()

{

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

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

    {

        input();

        printf("%d\n", dinic(, n - ));

    }

    return ;

}