Pagini recente » Cod sursa (job #2276744) | Cod sursa (job #1687244) | Cod sursa (job #1331825) | Cod sursa (job #1573649) | Cod sursa (job #301693)
Cod sursa(job #301693)
#include<stdio.h>
FILE *fin=fopen("harta.in","r"),
*fout=fopen("harta.out","w");
int N,S,D,M[210][210],A[210],flux;
int coada[500];
char viz[500];
int main(){
fscanf(fin,"%d",&N);
S=0,D=N+N+1;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
M[i][j+N]=1;
for(int i=1;i<=N;i++){
fscanf(fin,"%d %d",&M[S][i],&M[N+i][D]);
M[i][i+N]=0;
}
int ok=1;
while(ok){
ok=0;
A[S]=-1;
for(int i=1;i<=D;i++)
viz[i]=0;
viz[S]=1;
int li=1,lf=1;
coada[1]=S;
viz[S]=1;
while(li<=lf){
int x=coada[li++];
for(int i=0;i<=D;i++)
if(M[x][i] && viz[i]==0){
A[i]=x;
if(i==D)
ok=1;
coada[++lf]=i;
viz[i]=1;
}
}
if(ok){
for(int i=D;A[i]!=-1;i=A[i])
--M[A[i]][i],++M[i][A[i]];
++flux;
}
}
fprintf(fout,"%d\n",flux);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(M[j+N][i])
fprintf(fout,"%d %d\n",i,j);
fclose(fin);
fclose(fout);
return 0;
}