Cod sursa(job #782721)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 29 august 2012 13:44:46
Problema Taramul Nicaieri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#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;
}