Pagini recente » Cod sursa (job #1011487) | Cod sursa (job #1517599) | Cod sursa (job #491169) | Cod sursa (job #182974) | Cod sursa (job #5019)
Cod sursa(job #5019)
#include<stdio.h>
#include<string.h>
int n, c[304][304], out[101], in[101], f[304][304];
void afis()
{
int sum=0;
for(int i=1; i<=n; ++i) sum+= in[i]+out[i];
printf("%d\n",sum/2);
for(int i=0; i<=2*n+1; ++i) {
for(int j=0; j<=2*n+1; ++j) if(f[i][j]>0 && i!=0 && j!=2*n+1) printf("%d %d\n",(i+1)/2,j/2);
}
}
void init()
{
for(int i=1; i<=n; ++i) {
c[0][2*i-1] = out[i];
c[2*i][2*n+1] = in[i];
for(int j=1; j<=n; ++j) if(i!=j) c[2*i-1][2*j]= 1;
}
}
int BFS()
{
int Q[1000], p=1, q=1, pred[303], viz[303];
memset(viz, 0, sizeof(viz));
memset(pred,-1, sizeof(pred));
memset(Q,0,sizeof(Q));
p=1;
q=1;
Q[1]= 0;
viz[0]=1;
while(p<=q) {
for(int i=1; i<= 2*n+1; ++i) if(!viz[i] && c[Q[p]][i]- f[Q[p]][i] > 0 ) {
Q[++q]= i;
pred[i]= Q[p];
viz[i]= 1;
}
p++;
}
if(!viz[2*n+1]) return 0;
int min=1;
p= 2*n+1;
while(p) {
f[pred[p]][p]+=min;
f[p][pred[p]]-=min;
p=pred[p];
}
return 1;
}
int main()
{
freopen("harta.in","r",stdin);
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%d %d",&out[i], &in[i]);
init();
freopen("harta.out","w",stdout);
while(BFS()) ;
afis();
return 0;
}