Cod sursa(job #2205662)

Utilizator biaiftimeIftime Bianca biaiftime Data 19 mai 2018 20:22:48
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <vector>
#include <queue>

#define Nmax 202
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

int C[Nmax][Nmax],F[Nmax][Nmax];
int n,m;
vector < int > d1; //nr de drumuri care pleaca din orasul i
vector < int > d2; //nr de drumuri care intra in orasul i
void Read()
{
    int i;
    fin>>n;
    d1.resize(n+1);
    d2.resize(n+1);
    for(i=1;i<=n;++i)
        {
            fin>>d1[i]>>d2[i];
            m+=d1[i];
        }
}
void Initializare()
{
    int i,j;
    for(i=1;i<=n;++i)
        for(j=n+1;j<=2*n;++j)
            if(j-i!=n)C[i][j]=1;
    for(j=1;j<=n;++j)C[0][j]=d1[j];
    for(j=n+1;j<=2*n;++j)C[j][2*n+1]=d2[j-n];
}
int Flux(int s)
{
    queue<int>c;
    vector<int>t(2*n+2);
    vector<int>viz(2*n+2);
    int x,i;
    c.push(s); viz[s]=1;
    while(!c.empty())
    {
        x=c.front();
        c.pop();
        for(i=1;i<=2*n+1;++i)
            if(viz[i]==0)
        {
            if(F[x][i]==C[x][i])
                continue;
            c.push(i);
            viz[i]=1;
            t[i]=x;
        }
    }
    if(viz[2*n+1]==0)return 0;
    for(x=2*n+1;x!=s;x=t[x])
    {
        F[t[x]][x]+=1;
        F[x][t[x]]-=1;
    }
    return 1;
}
int main()
{
    Read();
    Initializare();
    while(true)
    {
        int acum = Flux(0);
        if(acum == 0)
            break;
    }
    fout<<m<<"\n";
    int i,j;
    for(i=1;i<=n;++i)
        for(j=n+1;j<=2*n;j++)
            if(F[i][j]==1) fout<<i<<" "<<j-n<<"\n";
    return 0;
}