Pagini recente » Cod sursa (job #583955) | Cod sursa (job #1217156) | Cod sursa (job #1504050) | Cod sursa (job #1440681) | Cod sursa (job #2961398)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n; // noduri
int m; // muchii
int s; // nod sursa
int t; // nod destinatie
vector<int> adj[MAX_N]; // lista de adiacenta
int cap[MAX_N][MAX_N]; // capacitate
int flow[MAX_N][MAX_N]; // flux
int maxflow; // flux maxim
int parent[MAX_N]; // vector de distanta minima
// distanta de la s la t folosind bfs
bool bfs(int s, int t) {
memset(parent, -1, sizeof parent); // resetare parinte
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (parent[v] == -1 && cap[u][v] - flow[u][v] > 0) {
parent[v] = u;
q.push(v);
if (v == t) {
return true;
}
}
}
}
return false;
}
// ne folosim de Edmonds - Karp pentru flux maxim
int maxFlow(int s, int t) {
maxflow = 0;
while (bfs(s, t)) {
int f = INT_MAX;
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
f = min(f, cap[u][v] - flow[u][v]);
}
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
flow[u][v] += f;
flow[v][u] -= f;
}
maxflow += f;
}
return maxflow;
}
int main() {
// citire
fin >> n >> m;
s = 0; // sursa
t = n - 1; // destinatie
for (int i = 0; i < m; i++) {
int u, v, w;
fin >> u >> v >> w;
u--; // conversie 0-indexed
v--; // convversie 0-indexed
adj[u].push_back(v);
adj[v].push_back(u);
cap[u][v] = w;
}
// flux maxim
int maxflow = maxFlow(s, t);
// afisare
fout << maxflow << endl;
return 0;
}