Cod sursa(job #2415381)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 25 aprilie 2019 21:06:17
Problema Flux maxim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define NMAX 1005
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int n,m;

vector<int> adj[NMAX];
int weight[NMAX][NMAX];

int flow;
bool vis[NMAX];

int dfs(int v,int minEdge,int lim)
{
    //cout<<v<<' '<<minEdge<<'\n';
    vis[v]=1;
    if(v==n)
    {
        flow+=minEdge;
        return minEdge;
    }
    for(auto u:adj[v])
    {
        int result=0;
        if(!vis[u]&&weight[v][u]>=lim)
            result=dfs(u,min(minEdge,weight[v][u]),lim);
        if(result)
        {
            weight[v][u]-=result;
            weight[u][v]+=result;
            return result;
        }
    }
    return 0;
}


int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,w;
        fin>>x>>y>>w;
        adj[x].push_back(y);
        adj[y].push_back(x);
        weight[x][y]=w;
    }
    int flowIncrease;
    int lim=(1<<10);
    do
    {
        flowIncrease=dfs(1,0x3f3f3f3f,lim);
        if(flowIncrease==0)
            lim>>=1;
        memset(vis,0,sizeof(vis));
    }
    while(flowIncrease||lim>=1);

    fout<<flow;
    return 0;
}