#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
#include <list>
#include <queue>
using namespace std;

const int N = 100;

int c[N][N], //有向边的容量
cf[N], //（（到达各顶点的增广路径）的各条边权值）的最小值
f[N][N], //流
n, //顶点数
prev[N]; //增广路中顶点的前驱
list<int> near[N]; //邻接表

bool BFS()
{
   queue<pair<int, int> > q;
   q.push(make_pair(0, 0));
   prev[0] = -2;
   memset(prev+1, 0xFF, sizeof(prev[0])*(n-1));
   cf[0] = INT_MAX;
   while (!q.empty() && prev[n-1] == -1)
   {
        pair<int, int> curr = q.front();
        q.pop();
        for (list<int>::iterator iter = near[curr.first].begin(); iter != near[curr.first].end(); ++iter)
        {
            if (c[curr.first][*iter] > f[curr.first][*iter] && prev[*iter] == -1)
            {
                q.push(make_pair(*iter, curr.second+1));
                prev[*iter] = curr.first;
                cf[*iter] = min(cf[curr.first], c[curr.first][*iter]-f[curr.first][*iter]);
            }
        }
   }
   return prev[n-1] != -1;
}

int Edmonds_Karp()
{
   int res = 0;

   //构造邻接表
   for (int i = 0; i < n-1; ++i)
        for (int j = i; ++j < n; )
            if (c[j] > 0 || c[j] > 0)
            {
                near.push_back(j);
                near[j].push_back(i);
            };

   while (BFS()) //残留网络中存在从源到汇的增广路经
   {
        for (int i = n-1; i; i = prev)
        {
            f[prev] += cf[n-1];
            f[prev] = -f[prev];
        }
        res += cf[n-1];
   }
   return res;
}

int main()
{
   int m;
   while (scanf("%d%d", &m, &n) != EOF) //输入边数和顶点数
   {
        for (int i = 0; i < n; ++i)
        {
            memset(c, 0, sizeof(c[0][0])*n);
            memset(f, 0, sizeof(f[0][0])*n);
            near.clear();
        }
        for (; m; --m)
        {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            c[x][y] = w;
        }
        printf("%d\n", Edmonds_Karp()); //计算从0（源）到 n-1（汇）的最大流
   }
}

Disclaimer: some contents on this website are collected through internet etc. Please notify if violated the original author's copyright and we will delete it immediately.
免责声明：本站部分文章来源于网络等其它媒体，如果侵犯了原作者的版权，请联系我们，本站将立即删除。