Cod sursa(job #1438744)

Utilizator emiiMihailescu Ionut Emanuel emii Data 20 mai 2015 18:54:59
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 1.29 kb
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,in[206],ies[206],c[206][206],F[206][206],v[206],t[206];
int bfs()
{
    int k,u,cd[206];
    cd[0]=1;cd[1]=0;
    for(int i=1;i<=2*n+1;i++)
        v[i]=t[i]=0;
    v[0]=1;
    for(int j=1;j<=cd[0];j++)
    {
        k=cd[j];u=2*n+1;
        for(int i=1;i<=u;i++)
            if(c[k][i]>F[k][i]&& v[i]==0)
        {
            t[i]=k;v[i]=1;
            if(i==u)
                return 1;
            cd[0]++;cd[cd[0]]=i;
        }
    }
    return v[2*n+1];
}
int main()
{f>>n;
for(int i=1;i<=n;i++)
    {f>>ies[i]>>in[i];
    c[0][i]=ies[i];
    c[n+i][2*n+1]=in[i];
    }
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(i!=j)
            c[i][n+j]=1;
int u,z,k;
t[0]=-1;
while(bfs())
{
    z=2*n+1;k=10000000;
    while(z)
    {
        if(k>c[t[z]][z]-F[t[z]][z])
            k=c[t[z]][z]-F[t[z]][z];
        z=t[z];
    }
    z=2*n+1;
    while(z)
        F[z][t[z]]= F[z][t[z]]-k,F[t[z]][z]=F[t[z]][z]+k,z=t[z];
}
int nr=0;
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(F[i][j+n]==1)
            nr++;
g<<nr<<'\n';
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(F[i][j+n]==1)
            g<<i<<" "<<j<<'\n';
return 0;
}