Pagini recente » Cod sursa (job #2641804) | Cod sursa (job #2442459) | Cod sursa (job #2729094) | Cod sursa (job #1591805) | Cod sursa (job #2454001)
//check check check
//#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<map>
#include<iomanip>
#define ll long long
#define pb(x) push_back(x)
using namespace std;
typedef pair<int,int> ii;
const int NMAX = 1005;
const int INF = 1e9;
vector<int>g[NMAX];
int capacity[NMAX][NMAX],flow[NMAX][NMAX];
int N,M,tata[NMAX];
int BFS(int source , int sink)
{
int i;
queue<ii>q;
for(i = 1 ; i <= N ; ++i)
tata[i] = 0;
tata[source] = -1;
q.push(ii(source , INF));
int node,curr_flow;
while(!q.empty())
{
node = q.front().first;
curr_flow = q.front().second;
q.pop();
if(node == N)
return curr_flow;
for(auto gnode : g[node])
{
if(tata[gnode] == 0 && capacity[node][gnode] > flow[node][gnode])
{
tata[gnode] = node;
q.push(ii(gnode , min(curr_flow , capacity[node][gnode] - flow[node][gnode])));
}
}
}
return 0;
}
int main()
{
freopen("maxflow.in" , "r" , stdin);
freopen("maxflow.out" , "w", stdout);
int i,j,x,c,y;
scanf("%d%d",&N,&M);
for(i = 1 ; i <= M ; ++i)
{
scanf("%d%d%d",&x,&y,&c);
g[x].pb(y);
g[y].pb(x);
capacity[x][y] = c;
}
int new_flow,source = 1 , sink = N , maxflow = 0;
while(new_flow = BFS(source , sink))
{
for(i = sink ; i != source ; i = tata[i])
{
flow[tata[i]][i] += new_flow;
flow[i][tata[i]] -= new_flow;
}
maxflow += new_flow;
}
printf("%d",maxflow);
return 0;
}