Pagini recente » Cod sursa (job #2238283) | Cod sursa (job #2154164) | Cod sursa (job #2802433) | Cod sursa (job #1384593) | Cod sursa (job #1553183)
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
vector<int> G[1001];
int N, M,a,b,c,i,T=0;
int viz[1001];
int from[1001],O[1001],A[1001][1001];
int BFS(int x)
{
queue<int> q;
q.push(x);
viz[x] = T+1;
int i;
while (q.size())
{
x = q.front();
q.pop();
for (i = 0; i < G[x].size();++i)
if (viz[G[x][i]]<=T && A[x][G[x][i]]>0)
{
q.push(G[x][i]);
viz[G[x][i]] = T+1;
from[G[x][i]] = x;
if (G[x][i] == N)
{
return 1;
}
}
}
return 0;
}
void update(int x)
{
int min_value = 1<<30;
int root = x;
if (A[from[from[x]]][from[x]] == A[from[x]][from[from[x]]])
return;
while (from[x])
{
min_value = min(min_value, A[from[x]][x]);
x = from[x];
}
if (min_value == 0)
return;
x = root;
while (from[x])
{
if (A[from[x]][x] - min_value >= 0)
{
A[from[x]][x] = A[from[x]][x] - min_value;
A[x][from[x]] = A[x][from[x]] + min_value;
}
else
{
A[from[x]][x] = A[from[x]][x] + min_value;
A[x][from[x]] = A[x][from[x]] - min_value;
}
x = from[x];
}
}
void Edmond()
{
while (BFS(1))
{
update(N);
++T;
}
}
int main()
{
in >> N >> M;
for (i = 1; i <= M; ++i)
{
in >> a >> b>>c;
G[a].push_back(b);
A[a][b] = c;
G[b].push_back(a);
}
for (i = 0; i < G[1].size(); ++i)
O[i] = A[1][G[1][i]];
Edmond();
int s = 0;
for (i = 0; i < G[1].size(); ++i)
s += O[i]-A[1][G[1][i]];
out << s;
return 0;
}