Cod sursa(job #563132)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 24 martie 2011 15:23:33
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<stdio.h>
#define maxN 105
#define Srs (N<<1)+1
#define Dst (N<<1)+2
#include<vector>
using namespace std;

FILE*f=fopen("harta.in","r");
FILE*g=fopen("harta.out","w");

int N,i,j,in,out,C[maxN << 1],Viz[maxN << 1],T[maxN << 1];
int Cp[maxN << 1][maxN << 1],F[maxN << 1][maxN << 1];

vector<int>A[maxN << 1];

void conecteaza(int nod1,int nod2,int c){
	A[nod1].push_back(nod2);
	A[nod2].push_back(nod1);
	Cp[nod1][nod2] = c;
}

int Bfs () {
	
	int ok = 0; int p,u;
	
	memset(Viz,0,sizeof(Viz));
	memset(T,0,sizeof(T));
	p = u = 1; C[1] = Srs; Viz[Srs] = 1;
	
	while ( p <= u ){
		int nod = C[p];
		
		for ( int i = 0 ; i < A[nod].size() ; ++i ){
			int nodvc = A[nod][i];
			
			if ( !Viz[nodvc] && Cp[nod][nodvc] > F[nod][nodvc] ){
				
				if ( nodvc == Dst ){
					ok = 1;
					continue;
				}
				
				++u; C[u] = nodvc;
				Viz[nodvc] = 1; T[nodvc] = nod;
				
			}
		}
		++p;
	}
	
	return ok;
	
}

int fluxmaxim () {
	int minim,nod,nodaux;
	int maxflow = 0;
	
	while ( Bfs() ){
		for ( int i = 0 ; i < A[Dst].size() ; ++i ){
			nod = A[Dst][i];
			
			minim = Cp[nod][Dst] - F[nod][Dst];
			
			nodaux = nod;
			
			while ( T[nodaux] ){
				minim = min( minim , Cp[T[nodaux]][nodaux] - F[T[nodaux]][nodaux] );
				nodaux = T[nodaux];
			}
			
			T[Dst] = nod;
			
			nodaux = Dst;
			
			while ( T[nodaux] ){
				F[ T[nodaux] ][ nodaux ] += minim ;
				F[ nodaux ][ T[nodaux] ] -= minim ;
				nodaux = T[nodaux];
			}
			
			maxflow += minim;
			
		}
	}
	
	return maxflow;
	
}

int main () {
	fscanf(f,"%d",&N);
	for ( i = 1 ; i <= N ; ++i ){
		fscanf(f,"%d %d",&in,&out);
		conecteaza(Srs,i,in);
		conecteaza(i+N,Dst,out);
	}
	
	for ( i = 1 ; i <= N ; ++i ){
		for ( j = 1 ; j <= N ; ++j ){
			
			if ( i != j )
				conecteaza(i,j+N,1);
			
		}
	}
	
	fprintf( g,"%d\n",fluxmaxim() );
	
	for ( i = 1 ; i <= N ; ++i ){
		for ( j = 1 ; j <= N ; ++j ){
			
			if ( i != j && F[i][j+N] == 1 )
				fprintf(g,"%d %d\n",i,j);
			
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}