Pagini recente » Cod sursa (job #95052) | Cod sursa (job #2260067) | Cod sursa (job #571877) | Cod sursa (job #1029485) | Cod sursa (job #220165)
Cod sursa(job #220165)
#include<stdio.h>
#include<string.h>
#define L 202
int n,nr,a[L][L],v[L][L],w[L];
int bfs(){
int i,j,x,act,q[L];
memset(w,-1,sizeof(w));
x=0;
q[0]=0;
w[0]=-1;
for(j=0;j<=x;++j){
act=q[j];
for(i=0;i<=2*n+1;++i){
if(w[i]==-1&&a[act][i]>v[act][i]){
q[++x]=i;
w[i]=act;
if(i==2*n+1)
return true;
}
}
}
return false;
}
int main(){
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
int i,j,x,y,q;
for(i=1;i<=n;++i){
scanf("%d%d",&x,&y);
a[0][i]=x;
a[i+n][2*n+1]=y;
nr+=x;
for(j=1;j<=n;++j)
if(j!=i)
a[i][j+n]=1;
}
printf("%d\n",nr);
while(bfs()){
q=2*n+1;
while(q){
v[w[q]][q]++;
v[q][w[q]]--;
q=w[q];
}
}
for(i=1;i<=n;++i){
for(j=n+1;j<2*n+1;++j){
if(v[i][j]>0)
printf("%d %d\n",i,j-n);
}
}
return 0;
}