Cod sursa(job #592075)
#include <cstring>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 1 << 30;
int maxflow, n, m;
int c[1001][1001], f[1001][1001], t[1001];
bool s[1001];
queue<int> q;
vector<int> v;
inline int abs(int x)
{
return x < 0 ? -x : x;
}
bool bfs();
void dim();
int main()
{
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
fin >> n >> m;
for (int i = 1, nod1, nod2, cap; i <= m; ++i)
{
fin >> nod1 >> nod2 >> cap;
c[nod1][nod2] = cap;
}
while (bfs())
dim();
fout << maxflow;
}
bool bfs()
{
v.clear();
memset(s, 0, sizeof(s));
memset(t, 0, sizeof(t));
while (!q.empty()) q.pop();
q.push(1);
while (!q.empty())
{
int i = q.front(); q.pop();
if (f[i][n] < c[i][n])
{
v.push_back(i);
continue;
}
for (int j = 1; j <= n; ++j)
if (!s[j])
{
if (f[i][j] < c[i][j])
{
t[j] = i, s[j] = true;
q.push(j);
}
if (f[j][i] > 0)
{
t[j] = -i, s[j] = true;
q.push(j);
}
}
}
if (v.size()) return true;
return false;
}
void dim()
{
while (!v.empty())
{
int i = v.back();
int crnow = c[i][n] - f[i][n];
while (i != 1)
{
if (t[i] > 0) crnow = min(crnow, c[t[i]][i] - f[t[i]][i]);
else crnow = min(crnow, f[i][abs(t[i])]);
i = abs(t[i]);
}
i = v.back();
while (i != 1)
{
if (t[i] > 0) f[t[i]][i] += crnow;
else f[i][abs(t[i])] -= crnow;
i = abs(t[i]);
}
maxflow += crnow;
v.pop_back();
}
}