Cod sursa(job #741671)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 26 aprilie 2012 18:25:04
Problema Adapost Scor 54
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.91 kb
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>

#define maxn 405
#define pb push_back
#define mp make_pair
#define INF (1<<29)

using namespace std;

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

int n;
int L[maxn],R[maxn],viz[maxn];
double v[maxn*maxn],lim,Dist[maxn<<1];
int S,D;
int Cp[maxn<<1][maxn<<1],F[maxn<<1][maxn<<1],C[maxn<<1],inQ[maxn<<1],T[maxn<<1];
vector< pair<int,double> >G[maxn];
vector<int>V[maxn<<1]; queue<int>Q;
double cost[maxn<<1][maxn<<1];

struct pct{
	double x,y;
}A[maxn],B[maxn];

inline void citire () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
	}
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf",&B[i].x,&B[i].y);
	}
}

inline double dist ( const pct &a , const pct &b ){
	double d = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
	return sqrt(d);
}

bool pairup ( int nod ){
	if ( viz[nod] )	return 0;
	viz[nod] = 1;
	
	for ( vector< pair<int,double> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = itt->first; double cost = itt->second;
		if ( cost <= lim ){
			if ( !R[nodvcn] ){
				L[nod] = nodvcn; R[nodvcn] = nod;
				return 1;
			}
		}
	}
	
	for ( vector< pair<int,double> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = itt->first; double cost = itt->second;
		if ( cost <= lim ){
			if ( pairup(R[nodvcn]) ){
				L[nod] = nodvcn; R[nodvcn] = nod;
				return 1;
			}
		}
	}
	
	return 0;
}

inline bool cuplaj () {
	
	memset(L,0,sizeof(L)); memset(R,0,sizeof(R));
	int ok = 1;
	do{
		ok = 0; memset(viz,0,sizeof(viz));
		for ( int i = 1 ; i <= n ; ++i ){
			if ( !L[i] )
				ok |= pairup(i);
		}
	}while(ok);
	
	int cuplaj = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		if ( L[i] ){
			++cuplaj;
		}
	}
	
	return cuplaj == n;
}

inline void first () {
	
	int index = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= n ; ++j ){
			v[++index] = dist(A[i],B[j]);
			G[i].pb(mp(j,v[index]));
		}
	}
	sort(v+1,v+index+1);
	
	int p = 1,m,u = index;
	while ( p <= u ){
		m = (p + u) >> 1;
		lim = v[m];
		
		if ( cuplaj() ){
			u = m - 1;
		}
		else{
			p = m + 1;
		}
	}
	
	lim = v[p];
	fprintf(g,"%.5lf ",lim);
}

inline double abs ( const double &j ){
	if ( j < 0 )
		return -j;
	return j;
}

inline bool bellman_ford () {
	
	Q.push(S); inQ[S] = 1;
	
	for ( int i = 1 ; i <= D ; ++i ){
		Dist[i] = INF;
	}
	Dist[S] = 0;
	
	while ( !Q.empty() ){
		int nod = Q.front(); Q.pop(); inQ[nod] = 0;
		
		for ( vector<int>::iterator itt = V[nod].begin() ; itt != V[nod].end() ; ++itt ){
			int nodvcn = (*itt);
			if ( Dist[nodvcn] > Dist[nod] + cost[nod][nodvcn] && F[nod][nodvcn] < Cp[nod][nodvcn] && abs(cost[nod][nodvcn] <= lim) ){
				Dist[nodvcn] = Dist[nod] + cost[nod][nodvcn]; T[nodvcn] = nod;
				if ( !inQ[nodvcn] ){
					Q.push(nodvcn);
					inQ[nodvcn] = 1;
				}
			}
		}
	}
	
	return Dist[D] != INF;
}

inline void flux () {
	double flow_cost = 0;
	
	while ( bellman_ford() ){
		
		int nod;
		for ( nod = D ; T[nod] ; nod = T[nod] ){
			++F[T[nod]][nod];
			--F[nod][T[nod]];
		}
		
		flow_cost += Dist[D];
	}
	
	fprintf(g,"%.5lf\n",flow_cost);
}

inline void second () {
	S = n+n+1; D = n+n+2;
	
	for ( int i = 1 ; i <= n ; ++i ){
		V[S].pb(i); V[i].pb(S);
		Cp[S][i] = 1;
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= n ; ++j ){
			int nod = j + n;
			cost[i][nod] = dist(A[i],B[j]);
			
			if ( cost[i][nod] <= lim ){
				V[i].pb(nod); V[nod].pb(i);
				Cp[i][nod] = 1;
				cost[nod][i] = -cost[i][nod];
			}
		}
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		int nod = i + n;
		V[nod].pb(D);
		Cp[nod][D] = 1;
	}
	
	flux();
}

int main () {
	
	citire();
	first();
	second();
	
	fclose(f);
	fclose(g);
	
	return 0;
}