Pagini recente » Cod sursa (job #2775560) | Cod sursa (job #563370) | Cod sursa (job #1016984) | Cod sursa (job #25935) | Cod sursa (job #2387871)
#include <bits/stdc++.h>
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
const int DIM = 1007;
vector <int> v[DIM];
int capacity[DIM][DIM];
int parent[DIM];
bool vis[DIM];
queue <int> q;
int n;
bool bfs()
{
for(int i = 2; i <= n; i++)
vis[i] = 0;
vis[1] = 1;
q.push(1);
while(!q.empty())
{
int nod = q.front();
q.pop();
for(int i = 0; i < v[nod].size(); i++)
{
int urm = v[nod][i];
if(vis[urm] == 0 && capacity[nod][urm])
{
parent[urm] = nod;
vis[urm] = 1;
if(urm != n)
q.push(urm);
}
}
}
return vis[n];
}
int main()
{
int m;
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y, c;
in >> x >> y >> c;
v[x].push_back(y);
v[y].push_back(x);
capacity[x][y] += c;
}
int flow = 0;
while(bfs())
for(int j = 0; j < v[n].size(); j++)
{
int nod = v[n][j];
if(capacity[nod][n] == 0 || vis[nod] == 0)
continue;
parent[n] = nod;
int new_flow = 1e9;
for(int i = n; i != 1; i = parent[i])
new_flow = min(new_flow, capacity[parent[i]][i]);
flow += new_flow;
for(int i = n; i != 1; i = parent[i])
{
capacity[parent[i]][i] -= new_flow;
capacity[i][parent[i]] += new_flow;
}
}
out << flow;
}