Flow Problem hdu 3549

Problem - 3549

题目大意：有一个有n个点的，求1到n的最大流

1<=n<=15

思路：从起点开始寻找能够到达终点的路径，并找出这条路径上的最小容量，沿着这条路每条边的容量对应减少，反向边增加，直至找不到这样一条路径为止

#include
using namespace std;
const int N = 1e3 + 5;
int g[20][20];//邻接矩阵存图
int pre[20], cnt = 0;
bool vis[20];
int n, m;
int mi = 1000;
bool bfs(int s, int t)
{//验证在残余网络中是否有增广路
    memset(pre, -1, sizeof pre);
    memset(vis, 0, sizeof vis);
    queue<int>q;
    mi = 1000;
    vis[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i=1;i<=n;i++)
        {
            if (!vis[i] && g[u][i]!=0)
            {
                vis[i] = 1;
                pre[i] = u;//记录路径
                q.push(i);
                mi = min(mi, g[u][i]);//记录最小容量
                if (i == t)//到达终点
                    return 1;
            }
        }
    }
    return 0;
}
int ek(int s, int t)
{
    int ans = 0, flow = 0;
    while (bfs(s, t))
    {
        flow = mi;//这个增广路的最小容量
        ans += flow;
        int u = t;
        while (u != s)
        {
            g[pre[u]][u] -= flow;//沿路径的容量减
            g[u][pre[u]] += flow;//反向路径容量+
            u = pre[u];
        }
    }
    return ans;
}
int main()
{
    int t;
    cin >> t;
    for (int cas = 1; cas <= t; cas++)
    {
        scanf("%d%d", &n, &m);
        memset(g, 0, sizeof g);
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u][v] += w;
        }
        printf("Case %d: %d\n", cas,ek(1, n));
    }
    return 0;
}