Cod sursa(job #420459)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 19 martie 2010 11:46:29
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<fstream>
#include<cstdio>
#include<vector>
using namespace std;

#define D 2*n+1
#define S 0
#define DIM 202
#define INFI 2000000000
#define pb push_back

int cap[DIM][DIM], t[DIM], n, fluxmax;

void citire()
{
    int i, j;
    ifstream fin("harta.in");
    fin>>n;
    for(i=1;i<=n; i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                cap[i][j+n]=1;
    for(i=1;i<=n;i++)
    {
        int ies, intra;
        fin>>ies>>intra;
        cap[S][i]=ies;
        cap[i+n][D]=intra;
    }
}

int bfs(int start, int end)
{
    vector<int> coada;
    int st, dr, k, i;
    st=dr=0;
    coada.pb(start);
    for(i=0;i<=D;i++)
        t[i]=-2;
    t[start]=-1;
    while(st<=dr)
    {
        k=coada[st++];
        for(i=0; i<=D;++i)
            if(t[i]==-2 && cap[k][i])
            {
                t[i]=k;
                if(i==D)
                {
                    coada.clear();
                    return 1;
                }
                coada.pb(i);
                dr++;
            }
    }
    coada.clear();
    return 0;
}

void e_k()
{
    int cmin,k;
    while(bfs(S,D))
    {
        cmin=INFI;
        for(k=D; t[k]!=-1 ; k=t[k])
            if(cap[t[k]][k]<cmin)
                cmin=cap[t[k]][k];
        fluxmax+=cmin;
        for(k=D; t[k]!=-1 ; k=t[k])
        {
            cap[t[k]][k]-=cmin;
            cap[k][t[k]]+=cmin;
        }
    }
}

void afis()
{
    int i,j;
    printf("%d\n",fluxmax);
    for(i=1;i<=n;i++)
        for(j=n+1;j<D;j++)
            if(i!=j-n && cap[i][j]==0)
                printf("%d %d\n", i, j-n);
}

int main()
{
    freopen("harta.out","w",stdout);
    citire();
    e_k();
    afis();
    return 0;
}