#include <iostream>
#include <queue>
#include <
string.h>
#define MAX 302
using namespace std;
int c[MAX][MAX];
int pre[MAX];
int visited[MAX];
int n, m;
bool Path(
int src,
int des)
{
queue <
int>
q;
for (
int i =
0; i <= m; i++
)
{
visited[i] =
0;
pre[i] =
0;
}
q.push(src);
visited[src] =
1;
while (!
q.empty())
{
int cur =
q.front();
q.pop();
for (
int i =
1; i <= m; i++
)
{
if (!visited[i] &&
c[cur][i])
{
q.push(i);
pre[i] =
cur;
visited[i] =
1;
if (i ==
des)
{
return true;
break;
}
}
}
}
return false;
}
int EK(
int src,
int des)
{
int min, i, total =
0;
while (
true)
{
if (!
Path(src, des))
{
break;
}
i =
des;
min = (
1 <<
30);
while (i !=
src)
{
if (min >
c[pre[i]][i])
{
min =
c[pre[i]][i];
}
i =
pre[i];
}
i =
des;
while (i !=
src)
{
c[pre[i]][i] -=
min;
c[i][pre[i]] +=
min;
i =
pre[i];
}
total +=
min;
}
return total;
}
int main()
{
int a, b, f;
while (cin >> n >>
m)
{
memset(c, 0,
sizeof(c));
for (
int i =
0; i < n; i++
)
{
cin >> a >> b >>
f;
c[a][b] +=
f;
}
cout << EK(
1, m) <<
endl;
}
return 0;
}
网络流的EK算法,主要就是不断的找增广路,如果找到了增广路,说明流量还可以增加,否则输出最大流即可.
找增广路用到bfs,找到后必须更新残量网络,用增广路的最大流更新残量网络.
转载于:https://www.cnblogs.com/lihek/p/3223596.html
相关资源：最大流EK算法
