Cod sursa(job #884841)

Utilizator deea101Andreea deea101 Data 21 februarie 2013 13:18:26
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <vector>
#include <list>
#define nmax 203
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> vec[nmax];
list <int> coada;
int n,d,viz[nmax],flux[nmax][nmax],tata[nmax];

int bfs()
{
    int i,j,nod;
    for(i=1;i<=d;i++) viz[i]=0;
    viz[1]=1;
    coada.push_back(1);
    while(!coada.empty())
    {
        nod=coada.front();
        for(i=0;i<vec[nod].size();i++)
        {
            j=vec[nod][i];
            if(j==d && flux[nod][d]) {viz[d]=1; continue;}
            if(viz[j] || !flux[nod][j]) continue;

            viz[j]=1; tata[j]=nod;
            coada.push_back(j);
        }
        coada.pop_front();
    }
    return viz[d];
}
int main()
{
    int x,y,i,j,fmin,fmax=0;
    f>>n;
    d=2*n+2;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        vec[1].push_back(i+1);
        vec[i+1].push_back(1);
        vec[i+n+1].push_back(d);
        vec[d].push_back(i+n+1);
        flux[1][i+1]=x;
        flux[i+n+1][d]=y;
    }
    for(i=2;i<=n+1;i++)
    {
        for(j=n+2;j<=2*n+1;j++)
        {
            if(j-i==n) continue;
            vec[i].push_back(j);
            vec[j].push_back(i);
            flux[i][j]=1;
        }
    }
    int nod;
    while(bfs())
    {
        for(j=0;j<vec[d].size();j++)
        {
            nod=vec[d][j];
            tata[d]=nod;
            fmin=100000;
            for(i=d;i!=1;i=tata[i])
            {
                if(flux[tata[i]][i]<fmin) fmin=flux[tata[i]][i];
            }
            if(!fmin) continue;
            for(i=d;i!=1;i=tata[i])
            {
                flux[tata[i]][i]-=fmin;
                flux[i][tata[i]]+=fmin;
            }
            fmax+=fmin;
        }
    }

    g<<fmax<<'\n';
    for(i=n+2;i<=2*n+1;i++)
    {
        for(j=2;j<=n+1;j++)
        {
            if(flux[i][j]) g<<j-1<<' '<<i-n-1<<'\n';
        }
    }
}