Pagini recente » Atasamentele paginii Bitconnect | Borderou de evaluare (job #2818543) | Borderou de evaluare (job #682152) | Borderou de evaluare (job #2270857) | Cod sursa (job #457536)
Cod sursa(job #457536)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#define Nmax 1001
using namespace std;
vector< pair< int, int > > G[Nmax];
vector< int > uz, cap;
vector< vector< int > > F;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int N, M, x, y, c, S, D, flux;
bool ek()
{
int fmin, loc;
uz.assign(N+1, 0);
cap.assign(N+1,0);
queue< int > Q;
Q.push(S);
while (!Q.empty())
{
loc = Q.front();
Q.pop();
for (vector< pair< int, int > >::iterator it = G[loc].begin(); it != G[loc].end(); ++it)
{
if (it->second > F[loc][it->first] && !uz[it->first])
{
uz[it->first] = loc;
cap[it->first] = it->second;
Q.push(it->first);
}
}
}
if (!uz[D]) return false;
fmin = cap[D] - F[uz[D]][D];
for (loc = uz[D]; loc != S; loc = uz[loc])
{
if (fmin > cap[loc] - F[uz[loc]][loc])
fmin = cap[loc] - F[uz[loc]][loc];
}
for (loc = D; loc != S; loc = uz[loc])
{
F[uz[loc]][loc] += fmin;
F[loc][uz[loc]] -= fmin;
}
return true;
}
int main()
{
fin >> N >> M;
F.assign(N+1,vector<int>(N+1,0));
for (int i = 0; i < M; ++i)
{
fin >> x >> y >> c;
G[x].push_back(make_pair(y,c));
//G[y].push_back(make_pair(x,c));
}
S = 1; D = N;
while(ek());
for (int i = 1; i <= N; ++i)
{
flux += F[i][D];
}
fout << flux;
//system("pause");
return 0;
}