Cod sursa(job #159425)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 14 martie 2008 09:38:52
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>      
#include<string.h>
#define N 210
#define ABS( a ) ( (a) < 0 ) ? - a : a
int gext[N],gint[N],FLOW[N][N],CAP[N][N];      
int S[N],Q[N],T[N];   
int n,i,j,sursa,dest,flow=0;
void solv( int start ){      
    int p, u, nod;      
    memset(S,0,sizeof(S));      
    memset(T,0,sizeof(T));      
    p=1;
	u=1;
	Q[p]=start;
	T[start]=-1;
	S[start]=1;      
    while((p<=u)&&(!S[dest])){      
        nod=Q[p];      
        for(i=sursa;i<=dest;i++ )      
            if(!S[i])
				if(CAP[nod][i] - FLOW[nod][i] > 0 ){   
					T[i]=nod;
					u++;
					Q[u]=i;
					S[i]=1;      
				}
				else 
					if (FLOW[i][nod] > 0 ){      
						T[i]=-nod;
						u++;
						Q[u]=i;
						S[i]=1;      
			}
		p++;
	}
}
void RELAX( int xp ){ 
    int t;      
    while(T[xp]!=-1){      
        t=ABS(T[xp]);      
        if(T[xp]>0)
			FLOW[t][xp]++;
		else 
			FLOW[xp][t]--;      
        xp=t;
    }      
}
int main(){
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%d\n",&n);
	for(i=1;i<=n;i++)
		scanf("%d %d\n",&gext[i],&gint[i]);
	sursa=1;
	dest=2*n+2;
	memset(CAP,0,sizeof(CAP) );
	memset(FLOW,0,sizeof(FLOW) );
	for(i=2;i<=n+1;i++)
		CAP[sursa][i]=gext[i-1];
	for(i=n+2;i<dest;i++)
		CAP[i][dest]=gint[i-n-1];
	for(i=2;i<=n+1;i++)
		for(j=n+2;j<dest;j++)
			CAP[i][j]=1;
	for(i=2;i<=n+1;i++)
		CAP[i][i+n] = 0;
	flow=0;
	do{
        solv(sursa);   
        if(S[dest]){
			flow++;
			RELAX(dest);
		}
	}while(S[dest]);
	printf("%d\n",flow);
	for(i=2;i<=n+1;i++)
		for(j=n+2;j<dest;j++)
			if(FLOW[i][j])
				printf("%d %d\n",i-1,j-n-1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}