Pagini recente » Cod sursa (job #2525608) | Cod sursa (job #1407878) | Cod sursa (job #1692505) | Cod sursa (job #126276) | Cod sursa (job #786229)
Cod sursa(job #786229)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
std::ifstream f("maxflow.in");
std::ofstream g("maxflow.out");
const int MAX_N = 1001;
int near[MAX_N], pnear; // From those, dest is 1 step away
int graph[MAX_N][MAX_N];
std::vector<int> neigh[MAX_N];
int parent[MAX_N];
int n, m;
int maxflow;
void build_graph()
{
int u, v, c;
f >> n >> m;
for (int i = 0; i < m; i ++) {
f >> u >> v >> c;
graph[u][v] = c;
neigh[u].push_back(v);
neigh[v].push_back(u);
}
}
void bfs(int source)
{
int qu[MAX_N * 2];
int first, last;
qu[0] = source;
first = last = 0;
memset(parent, 0, (n + 1) * sizeof(int));
pnear = 0;
while (first <= last) {
int u = qu[first++];
int v;
if (u == n) {
continue;
}
for (int i = 0; i < (int) neigh[u].size(); i ++) {
v = neigh[u][i];
if (graph[u][v] && parent[v] == 0) {
qu[++last] = v;
parent[v] = u;
}
}
if (graph[u][n]) {
near[pnear ++] = u;
}
}
}
int pick_path(int u)
{
// Compute the maximum flow for a path that goes through the (u, n) edge.
int maxf = graph[u][n];
int v = u;
while (v != 1) {
maxf = std::min(maxf, graph[parent[v]][v]);
v = parent[v];
}
if (maxf == 0) {
return 0;
}
// Saturate the path.
graph[u][n] -= maxf;
graph[n][u] += maxf;
v = u;
while (v != 1) {
graph[parent[v]][v] -= maxf;
graph[v][parent[v]] += maxf;
v = parent[v];
}
return maxf;
}
void compute_flow()
{
bfs (1);
if (pnear == 0) {
return;
}
for (int i = 0; i < pnear; i ++) {
maxflow += pick_path(near[i]);
}
compute_flow();
}
int main()
{
build_graph();
compute_flow();
g << maxflow << '\n';
return 0;
}