hdu3549 Flow Problem（裸最大流）

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
#define MAXN 21
#define INF 1<<28

using namespace std;

int cap[MAXN][MAXN], pre[MAXN], vis[MAXN], maxflow[MAXN];
int Maxflow;
int n, m, i, j;

void init()
{
    int x, y, z;
    memset(cap, 0, sizeof(cap));
    memset(pre, 0, sizeof(pre));

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        cap[x][y] += z;//重边
    }
}

int min(int a, int b)
{
    return a>b?b:a;
}

int main()
{
    int T, u, k=1;
    scanf("%d", &T);
    while(T--)
    {

        init();
        queue<int>q;
        Maxflow = 0;

        while(1)
       {
        memset(maxflow, 0, sizeof(maxflow));
        memset(vis, 0, sizeof(vis));
        maxflow[1] = INF;


        q.push(1);
        while(!q.empty())
        {
             u = q.front();
             q.pop();
             for(int v=1; v<=n; v++)
             {
                 if(!vis[v] && cap[u][v]>0)
                    {
                        vis[v] = 1;
                        pre[v] = u;
                        q.push(v);
                        maxflow[v] = maxflow[u]<cap[u][v]?maxflow[u]:cap[u][v];
                    }
             }
        }
        if(maxflow[n]==0) break;

        for(int i=n; i!=1; i=pre[i])
        {
            cap[pre[i]][i]-=maxflow[n];
            cap[i][pre[i]]+=maxflow[n];
        }

       Maxflow += maxflow[n];
    }
      printf("Case %d: %d\n", k++, Maxflow);
    }
     return 0;
}