Cod sursa(job #2738755)

Utilizator betybety bety bety Data 6 aprilie 2021 12:22:38
Problema Flux maxim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
struct Op
{
    int dest;
    int cap;
    int ind;
};
vector<Op> vec[1005];
pair<int,int> pred[1005];
int n,m,x,y,c;
queue<int> q;
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y>>c;
        int a=vec[x].size();
        int b=vec[y].size();
        vec[x].push_back({y,c,b});
        vec[y].push_back({x,0,a});
    }
    int flow=0;
    do
    {
        for(int i=2;i<=n;++i)
            pred[i]={0,0};
        pred[1]={-1,-1};
        q.push(1);
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=0;i<vec[x].size();++i)
            if(vec[x][i].cap>0 and pred[vec[x][i].dest].first==0)
            {
                pred[vec[x][i].dest]={x,i};
                q.push(vec[x][i].dest);
            }
        }
        int add;
        if(pred[n].first!=0)
        for(int i=0;i<vec[n].size();++i)
        if(pred[vec[n][i].dest].first!=0)
        {
            int u=vec[n][i].dest;
            int r=vec[n][i].ind;
            add=vec[u][r].cap;
            for(int k=u;pred[k].first>0;k=pred[k].first)
                add=min(add,vec[pred[k].first][pred[k].second].cap);
            if(add==0)
                continue;
            flow+=add;
            vec[u][r].cap-=add;
            vec[n][i].cap+=add;
            for(int k=u;pred[k].first>0;k=pred[k].first)
            {
                vec[pred[k].first][pred[k].second].cap-=add;
                vec[k][vec[pred[k].first][pred[k].second].ind].cap+=add;
            }
        }
    }while(pred[n].first!=0);
    out<<flow<<'\n';
    return 0;
}