Pagini recente » Borderou de evaluare (job #594012) | Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2695499)
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int cap[1020][1020], flow[1020][1020];
int dist[1020];
vector<int> graph[1020];
int n, m;
bool bfs(int source, int destination) {
for(int i = 1; i <= n; i++) {
dist[i] = n + 10;
}
dist[source] = 0;
queue<int> q;
q.push(source);
while(!q.empty()) {
int node = q.front();
q.pop();
for(auto x : graph[node]) {
if(cap[node][x] > flow[node][x] and dist[x] > dist[node] + 1) {
dist[x] = dist[node] + 1;
q.push(x);
}
}
}
return dist[destination] != (n + 10);
}
int maxFlow(int node, int destination, int maximumFlow) {
if(maximumFlow == 0) return 0;
if(node == destination) return maximumFlow;
int totalFlow = 0;
for(auto x : graph[node]) {
if(dist[x] != dist[node] + 1) continue;
int currentFlow = maxFlow(x, destination, min(maximumFlow - totalFlow, cap[node][x] - flow[node][x]));
flow[node][x] += currentFlow;
flow[x][node] -= currentFlow;
totalFlow += currentFlow;
}
return totalFlow;
}
int main() {
fin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y, cost;
fin >> x >> y >> cost;
graph[x].push_back(y);
graph[y].push_back(x);
cap[x][y] += cost;
}
int total = 0;
int inf = INT_MAX;
while(bfs(1, n)) {
total += maxFlow(1, n, inf);
}
fout << total;
return 0;
}