Cod sursa(job #830001)

Utilizator elielisorElena Eli elielisor Data 6 decembrie 2012 09:53:54
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<string>
using namespace std;
int a[202][202],b[202][202],t[202],l[300];
int n,m,i,j,x,y;
ifstream f("harta.in");
ofstream g("harta.out");
inline int bf()
{
    int st,dr;
    st=0;
    dr=0;
    l[0]=0;
    //memset(t,0,sizeof(t));
    while(st<=dr)
    {
        x=l[st];
        for(i=1;i<=2*n+1;i++)
        if(a[x][i]-b[x][i]>0 && !t[i])
        {
            t[i]=x;
            l[++dr]=i;
            if(i==2*n+1)
            return 1;
        }
        st++;
    }
    return 0;
}

inline void flux()
{
    while(bf())
    {
        x=2*n+1;
    while(x!=0)
    {
        b[t[x]][x]++;
        b[x][t[x]]--;
        x=t[x];
    }
    }
    for(i=1;i<=n;i++)
        for(j=n+1;j<=2*n;j++)
        {if(i!=j-n && b[i][j]==1)
        g<<i<<" "<<j-n<<"\n";}
}

int main()
{

    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        a[0][i]=x;
        a[n+i][2*n+1]=y;
        m+=x;
    }
    g<<m<<"\n";
    for(i=1;i<=n;i++)
    for(j=n+1;j<=2*n;j++)
    if(i!=j-n)
    a[i][j]=1;
    flux();
    return 0;
}