Cod sursa(job #192155)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 31 mai 2008 01:21:42
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <cstring>
#define FIN "harta.in"
#define FOUT "harta.out"
#define MAX 10010
using namespace std;
int U[MAX],st[MAX],dr[MAX],n1=0,n2=0,N;
int v1[MAX],v2[MAX];
int clpd[110][110];


void iofile(void){

    freopen(FIN,"rt",stdin);
    freopen(FOUT,"wt",stdout);

    scanf("%d",&N);

    for (int i=1,x,y;i<=N;++i){

        scanf("%d%d",&x,&y);
        for (int j=1;j<=x;++j){ v1[++n1]=i;}
        for (int j=1;j<=y;++j){ v2[++n2]=i;}

    }

    fclose(stdin);

    return ;
}


int PairUp(int nod){

    if (U[nod]){return 0;}
    if (st[nod]){ clpd[v1[nod]][v2[st[nod]]]=0;}
    U[nod]=1;
    for (int i=1;i<=n2;++i){
        if (v1[nod]!=v2[i] && !clpd[v1[nod]][v2[i]]){
            if (!dr[i]){
                st[nod]=i;dr[i]=nod;
                clpd[v1[nod]][v2[i]]=1;
                return i;
            } else
            {
                int cv;
                if (cv=PairUp(dr[i])){
                    st[nod]=i;
                    dr[i]=nod;
                    clpd[v1[nod]][v2[i]]=1;
                }
            }   
        }
    }
    return 0;

}

void cuplaj(void){

    for (int i=1;i<=n1;++i){
        if (st[i]) continue;
            if (!PairUp(i)){
                memset(U,0,sizeof(U));
                PairUp(i);
            }
    }

    printf("%d\n",n1);
    for (int i=1;i<=n1;++i){
        printf("%d %d\n",v1[i],v2[st[i]]);
    }

    fclose(stdout);

    return ;
}

int main(void){

    iofile();
    cuplaj();
    return 0;

}