【POJ 1273】Drainage Ditches（网络流）

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int arc[201][201], d[201], q[201];
int m, n, ans,tans;
bool bfs()
{
    memset(d, -1, sizeof d);
    queue<int>q;
    q.push(1);
    d[1] = 0;
    while(!q.empty())
    {
        int i,k=q.front();
        q.pop();
        for(i = 1; i <= n; i++)
            if(arc[k][i] > 0 && d[i] == -1)
            {
                d[i] = d[k] + 1;
                q.push(i);
            }
    }
    return d[n]>0;
}
int dinic (int k, int low)
{
    if(k == n)return low;
    int a,i;
    for(i = 1; i <= n; i++)
        if(d[i] == d[k] + 1&&  arc[k][i] > 0 &&(a = dinic(i, min(low, arc[k][i]))))
        {
                arc[k][i] -= a;
                arc[i][k] += a;
                return a;
        }
    return 0;
}
int main()
{
    while(~scanf("%d%d", &m, &n))
    {
        memset(arc, 0, sizeof arc);
        for(int i = 0; i < m; i++)
        {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            arc[u][v] += c;
        }
        ans = 0;
        while(bfs())
            while(tans=dinic(1, 0X3f3f3f3f)) ans += tans;
        printf("%d\n",ans);
    }
    return 0;
}