Cod sursa(job #574848)

Utilizator avram_florinavram florin constantin avram_florin Data 7 aprilie 2011 16:51:56
Problema Adapost Scor 37
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>

using namespace std;

const int MaxN = 401;
const double INF = 20000000.0;

int n,lg,S,cp,D,inQ[MaxN],T[MaxN],C[2*MaxN+5][2*MaxN+5],F[2*MaxN+5][2*MaxN+5];
float sol,sum,flux,d[MaxN][MaxN],dist[MaxN],P[MaxN*MaxN];
pair<float,float> Soldat[MaxN],Adapost[MaxN];
vector< vector< pair<int,float> > > G;
queue<int> Q;

void read()
{
	freopen( "adapost.in" , "r" , stdin );
	scanf("%d" , &n );
	S = (n<<1)+1;
	D = S+1;
	int i,j;
	for( i = 1 ; i <= n ; i++ )
		scanf("%f%f" , &Soldat[i].first , &Soldat[i].second );
	for( i = 1 ; i <= n ; i++ )
		scanf("%f%f" , &Adapost[i].first , & Adapost[i].second );
	for( i = 1 ; i <= n ; i++ )
		for( j = 1 ; j <= n ; j++ )
			{
				d[i][j] = (Soldat[i].first-Adapost[j].first)*(Soldat[i].first-Adapost[j].first) + (Soldat[i].second-Adapost[j].second)*(Soldat[i].second-Adapost[j].second);
				d[i][j] = sqrt(d[i][j]);
				P[++lg] = d[i][j];
			}
	sort( P+1, P+lg+1 );
}

void construieste_graf(float val)
{
	int i,j;
	memset(C,0,sizeof(C));
	memset(F,0,sizeof(F));
	G.clear();
	G.resize(2*n+5);
	//de la sursa la nod;
	for( i = 1 ; i <= n ; i++ )
		{
			G[S].push_back(make_pair(i,0));
			G[i].push_back(make_pair(S,0));
			C[S][i] = 1;
		}
	//de la nod la destinatie
	for( i = n+1 ; i <= n<<1 ; i++ )
		{
			G[i].push_back(make_pair(D,0));
			G[D].push_back(make_pair(i,0));
			C[i][D] = 1;
		}
	//de la nod la nod;
	for( i = 1 ; i <= n ; i++ )
		for( j = 1; j <= n ; j++ )
			if(d[i][j] <= val)
				{
					G[i].push_back(make_pair(j+n,d[i][j]));
					G[j+n].push_back(make_pair(i,-d[i][j]));
					C[i][j+n] = 1;
				}
}

int BF()
{
	int i,nod;
	vector< pair<int,float> >::iterator it;
	memset(inQ,0,sizeof(inQ));
	memset(T,0,sizeof(T));
	for( i = 0 ; i <= D+1 ; i++ )
		dist[i] = INF;
	inQ[S] = 1;
	dist[S] = 0;
	Q.push(S);
	while( !Q.empty() )
		{
			nod = Q.front();
			Q.pop();
			if( nod == D )
				continue;
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				if( C[nod][it->first] > F[nod][it->first] && dist[it->first] > dist[nod] + it->second )
					{
						dist[it->first] = dist[nod] + it->second;
						T[it->first] = nod;
						if( !inQ[it->first] )
							{
								Q.push(it->first);
								inQ[it->first] = 1;
							}
					}
			inQ[nod] = 0;
		}
	if( dist[D] == INF )
		return 0;
	return 1;
}

void FLUX()
{
	int nod,fluxmin;
	flux = 0;
	cp = 0;
	while( BF() )
		{
			fluxmin = 2000000;
			for( nod = D ; nod != S ; nod = T[nod] )
				fluxmin = min(fluxmin,C[T[nod]][nod] - F[T[nod]][nod] );
			if( !fluxmin )
				continue;
			for( nod = D ; nod != S ; nod = T[nod] )
				{
					F[T[nod]][nod] += fluxmin;
					F[nod][T[nod]] -= fluxmin;
				}
			flux += (fluxmin*dist[D]);
			cp += fluxmin;
		}
}

int main()
{
	read();
	int li,ls,mij;
	li = 1;
	ls = n*n;
	while( li <= ls )
		{
			mij = (li+ls)>>1;
			construieste_graf(P[mij]);
			FLUX();
			if( cp == n )
				{
					sol = P[mij];
					sum = flux;
					ls = mij-1;
				}
				else
				li = mij+1;
		}
	freopen( "adapost.out" , "w" , stdout );
	printf("%.5f %.5f\n" , sol , sum );
	return 0;
}