Pagini recente » Diferente pentru utilizator/schropese30c intre reviziile 1 si 2 | Rezultatele filtrării | Cod sursa (job #8609) | Cod sursa (job #1137821) | Cod sursa (job #1934294)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
const int NMAX = 1001;
int n, m;
int f[NMAX][NMAX], c[NMAX][NMAX];
vvi v;
vi t;
vb viz;
inline void read() {
fin >> n >> m;
v = vvi(n + 1);
t = vi(n + 1);
viz = vb(n + 1);
int x, y, cap;
for (int i = 1; i <= m; ++i) {
fin >> x >> y >> cap;
v[x].push_back(y);
v[y].push_back(x);
c[x][y] = cap;
f[x][y] = 0;
c[y][x] = 0;
}
}
inline bool bfs() {
queue<int> q;
viz = vb(n + 1);
q.push(1);
viz[1] = 1;
int node;
while (q.size()) {
node = q.front();
q.pop();
if (node == n)
continue;
for (const int& other: v[node]) {
if (viz[other])
continue;
if (c[node][other] <= f[node][other])
continue;
viz[other] = 1;
t[other] = node;
q.push(other);
}
}
return viz[n];
}
inline void getMaxFlow() {
int minFlow, ansFlow = 0;
while (bfs()) {
for (const int& other: v[n]) {
if (!viz[other])
continue;
t[n] = other;
minFlow = 0x3f3f3f3f;
for (int node = n; node != 1; node = t[node]) {
minFlow = min(minFlow, c[t[node]][node] - f[t[node]][node]);
}
if (minFlow == 0)
continue;
for (int node = n; node != 1; node = t[node]) {
f[t[node]][node] += minFlow;
f[node][t[node]] -= minFlow;
}
ansFlow += minFlow;
}
}
fout << ansFlow;
}
int main()
{
read();
getMaxFlow();
fin.close();
fout.close();
return 0;
}