Pagini recente » Cod sursa (job #1836054) | Cod sursa (job #171088) | Cod sursa (job #1814208) | Cod sursa (job #1656418) | Cod sursa (job #192154)
Cod sursa(job #192154)
#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;
}