Cod sursa(job #2970320)

Utilizator flavigFlavian flavig Data 24 ianuarie 2023 21:29:17
Problema Flux maxim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.98 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cmath>

using namespace std;

int n,m;
int tata[1001], viz[1001];
vector<pair<int, int>> *la;
vector<pair<int, int>> *flux;


int construire_lant()
{
    int i,j,u,v,w,flx;
    
    for(i=1; i<=n; i++)
    {
        tata[i]=0;
        viz[i]=0;
    }

    queue<int> q;

    q.push(1);
    viz[1]=1;

    while(!q.empty())
    {
        u=q.front();
        q.pop();
        
        for(i=0;i<la[u].size();i++) //arcele directe
        {
            v=la[u][i].first;
            w=la[u][i].second; //capacitatea
            flx=flux[u][i].second; //fluxul trimis
            if(viz[v]==0 && w-flx>0)
            {
                q.push(v);
                viz[v]=1;
                tata[v]=u;
                if(v==n)
                    return 1;
            }
        }

        for(i=1;i<=n;i++)
            for(j=0;j<la[i].size();j++)
                if(la[i][j].first==u)
                    {
                        v=i;
                        w=la[i][j].second;
                        flx=flux[i][j].second;
                        if(viz[v]==0 && flx>0)
                        {
                            q.push(v);
                            viz[v]=1;
                            tata[v]=-u;
                            if(v==n)
                                return 1;
                        }
                    }
    }
    return 0;
}

void revizuieste_lant()
{
    int x,t,w,min_f=INT_MAX,i;
    vector<int> lant;
    x=n;
    while(x!=1)
    {
        t=tata[x];
        if(t>0)
        {    for(i=0;i<la[t].size();i++)
                if(la[t][i].first==x)
                    w=la[t][i].second - flux[t][i].second;
        }
        else
            {
            t=abs(t);
            for(i=0;i<la[x].size();i++)
                if(la[x][i].first==t)
                    w=flux[x][i].second;
            }
        min_f=min(min_f,w);
        x=t;
    }
    x=n;
    while(x!=1)
    {
        t=tata[x];
        if(t>0)
            {for(i=0;i<la[t].size();i++)
                    if(la[t][i].first==x)
                        flux[t][i].second+=min_f;}
        else
            {
            t=abs(t);
            for(i=0;i<la[x].size();i++)
                if(la[x][i].first==t)
                    flux[x][i].second-=min_f;
            }
        x=t;
    }
    
}


int main()
{
    ifstream f("maxflow.in");
    ofstream g("maxflow.out");

    la = new vector<pair<int, int>>[1001];
    flux = new vector<pair<int,int>>[1001];

    int x, y, c, i, j;

    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        la[x].push_back(make_pair(y, c));
        flux[x].push_back(make_pair(y, 0));
    }

    while(construire_lant()==1)
        revizuieste_lant();
    
    int s=0;
    for(i=0;i<flux[1].size();i++)
        s+=flux[1][i].second;

    g<<s<<endl;
    return 0;
}