Cod sursa(job #2735470)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 2 aprilie 2021 14:07:41
Problema Flux maxim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;
#define SERVER 0
const string nameFile="maxflow";
ifstream in (nameFile+".in");
ofstream out(nameFile+".out");
typedef pair<int, long long> Pii;
#if (SERVER)
    #define in cin
    #define out cout
#endif
const int nmax=1e3;
const long long oo=1e18;
int n, m, x, y, z;
vector <int> muchii[nmax+2];
int parent[nmax+2];
int capacity[nmax+2][nmax+2];
long long ffLow;
int source=1, sink;
int bfs(){
    fill(parent+1, parent+n+1, -1);
    parent[source]=-2;
    queue <Pii> q;
    q.push({source, oo});
    while(!q.empty()){
        Pii per=q.front();
        q.pop();
        int nod=per.first;
        for(auto &x:muchii[nod])
            if(parent[x]==-1&&capacity[nod][x]){
                parent[x]=nod;
                long long newFlow=min(per.second, 1LL*capacity[nod][x]);
                if(x==sink)
                    return newFlow;
                q.push({x, newFlow});
            }
    }
    return 0;
}
void flow(){
    while(true){
        int tt=bfs();
        if(!tt)
            break;
        ffLow+=tt;
        int nodAct=sink;
        while(nodAct!=source){
            int temp=parent[nodAct];
            capacity[temp][nodAct]-=tt;
            capacity[nodAct][temp]+=tt;
            nodAct=temp;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    in>>n>>m;
    sink=n;
    for(int i=1; i<=m; i++){
        in>>x>>y>>z;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
        capacity[x][y]=z;
    }
    flow();
    out<<ffLow<<"\n";
    return 0;
}