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

const int N = 100;

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

bool BFS()
{
      queue<pair<int, int> > q;
      q.push(make_pair(src, 0));
      memset(level, -1, sizeof(level[0])*n);
      level[src] = 0;
      for (int i = 0; i < n; ++i)
            level_map.clear();
      while (!q.empty())
      {
            pair<int, int> curr = q.front();
            q.pop();
            for (list<int>::iterator iter = near[curr.first].begin(); iter != near[curr.first].end(); ++iter)
                  if (*iter != src && c[curr.first][*iter] > f[curr.first][*iter])
                  {
                        if (level[*iter] == -1)
                        {
                              level[*iter] = level[curr.first]+1;
                              level_map[curr.first].push_back(*iter);
                              q.push(make_pair(*iter, curr.second+1));
                        }
                        else if (level[*iter] == level[curr.first]+1)
                              level_map[curr.first].push_back(*iter);
                  };
      }
      return level[dst] != -1;
}

int Dinic()
{
      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()) //残留网络中存在从源到汇的增广路经
      {
            memset(hash, 0, sizeof(hash[0])*n);
            while (!hash[src])
            {
                  int i;
                  prev[src] = -1;
                  cf[src] = INT_MAX;
                  for (i = src; i != dst && i != -1; )
                  {
                        while (!level_map.empty() && hash[level_map.front()])
                              level_map.pop_front();
                        if (level_map.empty())
                        {
                              hash = true;
                              i = prev;
                              continue;
                        }
                        int j = level_map.front();
                        prev[j] = i;
                        cf[j] = min(cf, c[j]-f[j]);
                        level_map.pop_front();
                        i = j;
                  }
                  if (i == dst)
                  {
                        for (; i != src; i = prev)
                        {
                              f[prev] += cf[dst];
                              f[prev] = -f[prev];
                        }
                        res += cf[dst];
                  }
            }
      }
      return res;
}

int main()
{
      int m;
      while (scanf("%d%d", &m, &n) != EOF) //输入边数和顶点数
      {
            dst = n-1;
            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-1][y-1] += w;
            }
            printf("%d\n", Dinic()); //计算从 src（源）到 dst（汇）的最大流
      }
}

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