Pagini recente » Cod sursa (job #1230981) | Cod sursa (job #1894235) | Cod sursa (job #2882418) | Cod sursa (job #2332588) | Cod sursa (job #782721)
Cod sursa(job #782721)
#include<stdio.h>
#define dim 200
#define inf 2000000000
FILE*f=fopen("harta.in","r");
FILE*g=fopen("harta.out","w");
struct graf{
int nr;
graf *adr;
}*p,*c,*L[2*dim+100];
int n,i,j,x,y,viz[2*dim+10],nr,min,z,C[2*dim+10][2*dim+10],F[2*dim+10][2*dim+10],T[2*dim+10],s,R[2*dim][4];
void read(){
fscanf(f,"%d",&n);
for(i=1;i<=n;i++){
p=new graf;
p->nr=i;
p->adr=L[0];
L[0]=p;
p=new graf;
p->nr=0;
p->adr=L[i];
L[i]=p;
}
for(i=1;i<=n;i++){
for(j=n+1;j<=2*n;j++){
if((i+n)==j)
continue;
p=new graf;
p->nr=j;
p->adr=L[i];
L[i]=p;
p=new graf;
p->nr=i;
p->adr=L[j];
L[j]=p;
C[i][j]=1;
}
}
for(i=n+1;i<=2*n;i++){
p=new graf;
p->nr=2*n+1;
p->adr=L[i];
L[i]=p;
p=new graf;
p->nr=i;
p->adr=L[2*n+1];
L[2*n+1]=p;
}
for(i=1;i<=n;i++){
fscanf(f,"%d%d",&x,&y);
C[0][i]=x;
C[n+i][2*n+1]=y;
}
}
int bfs(){
for(i=0;i<=2*n+1;i++)
viz[i]=0;
int D[2*dim+10];
int p=1,u=1,ok=0;
D[1]=0;viz[0]=1;
while(p<=u){
x=D[p];
if(x==2*n+1){
p++;
continue;
}
c=L[x];
while(c){
if(!viz[c->nr]&&(C[x][c->nr]>F[x][c->nr])){
D[++u]=c->nr;
viz[c->nr]=1;
T[c->nr]=x;
if(c->nr==(2*n+1))
ok=1;
}
c=c->adr;
}
p++;
}
return ok;
}
int main(){
read();
while(bfs()){
c=L[2*n+1];
while(c){
if(viz[c->nr] && (C[c->nr][2*n+1]>F[c->nr][2*n+1])){
T[2*n+1]=c->nr;
z=2*n+1;min=inf;
while(T[z]){
if( (C[T[z]][z]-F[T[z]][z])<min)
min=C[T[z]][z]-F[T[z]][z];
z=T[z];
}
if( T[z]>=0&&(C[T[z]][z]-F[T[z]][z])<min)
min=C[T[z]][z]-F[T[z]][z];
z=2*n+1;
while(min!=inf&&T[z]){
F[T[z]][z]+=min;
F[z][T[z]]-=min;
z=T[z];
}
if(T[z]<0)
continue;
F[T[z]][z]+=min;
F[z][T[z]]-=min;
}
c=c->adr;
}
}
for(i=1;i<=n;i++){
c=L[i];
while(c){
if(c->nr==0){
c=c->adr;
continue;
}
if(F[i][c->nr]==1){
s++;
R[s][0]=i;
R[s][1]=c->nr-n;
}
c=c->adr;
}
}
fprintf(g,"%d\n",s);
for(i=1;i<=s;i++){
for(j=0;j<=1;j++)
fprintf(g,"%d ",R[i][j]);
fprintf(g,"\n");
}
return 0;
}