Cod sursa(job #2756283)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 30 mai 2021 17:00:33
Problema Flux maxim Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;

const int dim=1e3+10;

int n,m,sursa,dest;
vector < int > V[dim],e(dim,0),h(dim,0);
vector < vector < int > > C(dim,vector< int > (dim,0)),F(dim,vector< int > (dim,0));

void INITIALIZER_POMPARE()
{
    for(int i=0;i<n;i++)
    {
        h[i]=0;
        e[i]=0;
    }
    h[sursa]=n;
    for(int nod:V[sursa])
    {
        int cap=C[sursa][nod];
        e[sursa]-=cap;
        e[nod]+=cap;

        C[sursa][nod]-=cap;
        C[nod][sursa]+=cap;

        F[sursa][nod]+=cap;
        F[nod][sursa]-=cap;
    }
}

void Pompare(int u,int v)
{
    int cant=min(C[u][v],e[u]);
    C[u][v]-=cant;
    C[v][u]+=cant;

    F[u][v]+=cant;
    F[v][u]-=cant;

    e[u]-=cant;
    e[v]+=cant;
}

void Ridicare(int u)
{
    int mini=n;
    for(int v:V[u])
        if(C[u][v]>0)
            mini=min(mini,h[v]);
    h[u]=mini+1;
}

void Descarcare(int u)
{
    int idx=0;
    while(e[u]>0)
    {
        if(idx==V[u].size())
        {
            Ridicare(u);
            idx=0;
        }
        int v=V[u][idx];
        if(C[u][v]>0 && h[u]==h[v]+1)
        {
            Pompare(u,v);
        }
        else
            idx++;
    }
}

void pompare_topologica()
{
    INITIALIZER_POMPARE();
    list < int > lista;
    list < int > ::iterator it;
    for(int i=0;i<n;i++)
        if(i!=sursa && i!=dest)
        {
            lista.pb(i);
        }
    it=lista.begin();
    while(it!=lista.end())
    {
        int u=*it;

        int old_height=h[u];
        Descarcare(u);

        if(h[u]>old_height)
        {
            lista.erase(it);
            lista.push_front(u);
            it=lista.begin();
        }
        it++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        a--;
        b--;
        V[a].pb(b);
        V[b].pb(a);

        C[a][b]=c;
        F[a][b]=0;
        F[b][a]=0;
    }
    sursa=0,dest=n-1;
    pompare_topologica();

    int ans=0;
    for(int nod:V[sursa])
        ans+=F[sursa][nod];
    g<<ans;

    return 0;
}