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

const int N = 100;

bool flag[N]; //顶点是否在队列 l 中
int c[N][N], //有向边的容量
e[N], //余流
f[N][N], //流
h[N], //高度
n; //顶点数
list<int> l, //待排除顶点
near[N]; //邻接表

void Push(int x, int y)
{
    int df = min(e[x], c[x][y]-f[x][y]);
    f[x][y] += df;
    f[y][x] = -f[x][y];
    e[x] -= df;
    e[y] += df;
}

void Relabel(int x)
{
   h[x] = n*2-1;
   for (list<int>::iterator iter = near[x].begin(); iter != near[x].end(); ++iter)
        if (h[*iter] < h[x] && c[x][*iter] > f[x][*iter])
            h[x] = h[*iter];
   ++h[x];
}

void Discharge(int x)
{
   list<int>::iterator iter = near[x].begin();
   while (e[x] > 0) //有余流
   {
        if (iter == near[x].end())
        {
            Relabel(x);
            iter = near[x].begin();
        }
        if (h[x] == h[*iter]+1 && c[x][*iter] > f[x][*iter])
        {
            Push(x, *iter);
            if (e[*iter] > 0 && !flag[*iter])
                l.push_back(*iter);
        }
        ++iter;
   }
}

int Push_Relabel()
{
   l.clear();

   //初始化前置流
   h[0] = n; e[0] = 0;
   memset(flag+1, 0, n-2); //1~n-2 不在 l 中
   flag[0] = true; flag[n-1] = true; //防止源、汇进入 l
   for (int i = 1; i < n; ++i)
   {
        h = 0;
        f[0] = c[0];
        f[0] = -c[0];
        e[0] -= c[0];
        e = c[0];
        if (c[0] > 0 && i != n-1)
        {
            l.push_back(i); //待排除顶点
            flag = true;
        }
   }

   //构造邻接表
   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 (!l.empty())
   {
        int x = l.front();
        Discharge(x);
        l.pop_front();
        flag[x] = false;
   }

   return e[n-1];
}

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", Push_Relabel()); //计算从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.
免责声明：本站部分文章来源于网络等其它媒体，如果侵犯了原作者的版权，请联系我们，本站将立即删除。