Cod sursa(job #431616)

Utilizator	Ionescu Robert Marius Robytzza	Data	1 aprilie 2010 11:03:33
Problema	Flux maxim	Scor	100
Compilator	cpp	Status	done
Runda	Arhiva educationala	Marime	1.68 kb

Raporteaza aceasta sursa

#include <stdio.h>
#include <vector>
#define IN "maxflow.in"
#define OUT "maxflow.out"
#define Lg 1001

using namespace std;

vector <long> V[Lg];
long Cost[Lg][Lg];
long T[Lg], n, m, x, y, Q[Lg];
long sf, Flux;

void citire()
{
    scanf ("%ld %ld",&n,&m);
    for (long i=0;i<m;i++)
    {
        scanf ("%ld %ld",&x, &y);
        V[x].push_back(y);
        V[y].push_back(x);
        scanf ("%ld",&Cost[x][y]);
    }
}

long ok()
{
    sf=0;
    for (long i=1;i<=n;i++)
        T[i]=0;
    T[1]=-1;
    Q[sf++]=1;
    for (long i=0;i<sf;i++)
        for (long k=0;k<V[Q[i]].size();k++)
        {
            if (T[V[Q[i]][k]] || Cost[Q[i]][V[Q[i]][k]]==0)
                continue;
            T[V[Q[i]][k]]=Q[i];
            Q[sf++]=V[Q[i]][k];
            if (V[Q[i]][k]==n)
                return 1;
        }
    return 0;
}

void solve()
{
    long fl,nod;
    while (ok())
    {
        for (long i=1;i<n;i++)
        {
            if (!T[i] || !Cost[i][n])
                continue;
            fl=Cost[i][n];
            nod=i;
            while (nod!=1)
            {
                fl=min(fl,Cost[T[nod]][nod]);
                nod=T[nod];
            }
            if (!fl)
                continue;
            Cost[i][n]-=fl;
            Cost[n][i]+=fl;
            nod=i;
            while (nod!=1)
            {
                Cost[T[nod]][nod]-=fl;
                Cost[nod][T[nod]]+=fl;
                nod=T[nod];
            }
            Flux+=fl;
        }
    }
    printf("%ld\n",Flux);
}

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);
    citire();
    solve();
    return 0;
}

infoarena informatica de performanta

Cod sursa(job #431616)