Cod sursa(job #181783)

Utilizator c_sebiSebastian Crisan c_sebi Data 18 aprilie 2008 22:43:24
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <stdio.h>

#define MAXN 205
#define min(x, y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?x:-x)

int n, m, s, d, viz[MAXN], Q[MAXN];
int C[MAXN][MAXN]; //capacitatea fiecarui arc
int F[MAXN][MAXN]; //fluxul fiecarui arc

void citire(void);
void ek(void); //Edmonds-Karp
void afisare(void);
int bfs(void);

int main(){
	citire();
	ek();
	afisare();
	return 0;
}

void citire(){
	FILE *f=fopen("harta.in", "r");
	int i, j, x, y;
	fscanf(f, "%d", &n);
	s=2*n+1; d=2*n+2;
	for(i=1; i<=n; i++){
		fscanf(f, "%d %d", &x, &y);
		C[s][i]=x; C[i+n][d]=y;
	}
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			if(i!=j)
				C[i][j+n]=1;
	n=2*n+2;
}

void afisare(){
	FILE *g=fopen("harta.out", "w");
	int i, j, vf=0;
	for(i=1; i<=n; i++) vf+=F[i][d];
	fprintf(g, "%d\n", vf);
	n=(n-2)/2;
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			if(F[i][j+n])
				fprintf(g, "%d %d\n", i, j);
	
}

void ek(){
	int i, a, b, lg, v;
	int L[MAXN];
	do{
		//marcam varfurile intr-o parcuregre in latime
		for(i=1; i<=n; i++) viz[i]=0;
		if(bfs()) return ;
		//determin lantul de ameliorare L
		L[0]=d; lg=0;
		a=b=10000;
		while(L[lg]!=s){
			++lg;
			L[lg] = abs(viz[L[lg-1]]);
			if(viz[L[lg-1]]>0)
				a = min(a, C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
			else if(viz[L[lg-1]]<0)
					b = min(b, F[L[lg-1]][L[lg]]);
		}
		v = min(a, b);
		for(i=lg; i>0; i--)
			if(viz[L[i-1]]>0)
				F[L[i]][L[i-1]]+=v;
			else
				F[L[i-1]][L[i]]-=v;
	} while(1);
}

int bfs(){
	//returneaza 1 daca destinatia retelei nu a fost marcata
	int p, u, i, x;
	Q[0]=s; p=u=0; viz[s]=1;
	while(p<=u && !viz[d]){
		x=Q[p++];
		for(i=1; i<=n; i++)
			if(!viz[i])
				if(F[x][i]<C[x][i]){
					viz[i]=x; Q[++u]=i;
				}
				else if(F[i][x]>0){
					viz[i]=-x; Q[++u]=i;
				}
		}
	return !viz[d];
}