Cod sursa(job #2587149)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 22 martie 2020 12:50:52
Problema Adapost Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <queue>
#include <iomanip>

using namespace std;

ifstream fin("adapost.in");
ofstream fout("adapost.out");

const int IINF = 0x3f3f3f3f;
const double DINF = 0x3f3f3f3f3f3f3f3f;
const int N = 410;
const int N2 = N*2;

struct vec2{
	double x, y;
};

double sq(double a){
	return a*a;
}

double pyt(const vec2 &a, const vec2 &b){
	return sqrt(sq(a.x-b.x)+sq(a.y-b.y));
}

int n;
vec2 lt[N], rt[N];
void read(){
	fin >> n;
	for(int i = 1; i <= n; ++i){
		vec2 &a = lt[i];
		fin >> a.x >> a.y;
	}
	for(int i = 1; i <= n; ++i){
		vec2 &a = rt[i];
		fin >> a.x >> a.y;
	}
}

vector<int> gra[N2];

int s, d;
int flo[N2][N2], cap[N2][N2];
double cst[N2][N2];
void bipartize(){
	s = 0, d = 2*n+1;
	for(int i = 1; i <= n; ++i){
		cap[s][i] = cap[i+n][d] = 1;
		gra[s].push_back(i);
		gra[i+n].push_back(d);
	}
	for(int a = 1; a <= n; ++a){
		for(int b = 1; b <= n; ++b){
			cap[a][b+n] = 1;
			cst[a][b+n] = pyt(lt[a], rt[b]);
			cst[b+n][a] = -cst[a][b+n];
			
			gra[a].push_back(b+n);
			gra[b+n].push_back(a);
		}
	}
}

queue<int> q;
bool inq[N2];
double dist[N2];
int dad[N2];
void bellnuke(){
	for(int i = s; i <= d; ++i){
		dist[i] = DINF;
	}
}

bool bellman(){
	bellnuke();
	q.push(s);
	dist[s] = 0;
	while(!q.empty()){
		int a = q.front();q.pop();
		inq[a] = false;
		for(auto b : gra[a]){
			double v = dist[a]+cst[a][b];
			if(v < dist[b] && flo[a][b] < cap[a][b]){
				dist[b] = v;
				dad[b] = a;
				if(!inq[b]){
					q.push(b);
					inq[b] = true;
				}
			}
		}
	}
	return dist[d] < DINF+1;
}

double maxi = 0, total = 0;
void maxflow(){
	int fmin = IINF;
	for(int x = d; x != s; x = dad[x]){
		fmin = min(fmin, cap[dad[x]][x] - flo[dad[x]][x]);
	}
	for(int x = d; x != s; x = dad[x]){
		flo[dad[x]][x] += fmin;
		flo[x][dad[x]] -= fmin;
	}
	total += dist[d];
}

void flowerize(){
	while(bellman()){
		maxflow();
	}
}

void solve(){
	bipartize();
	flowerize();
}

void write(){
	for(int a = 1; a <= n; ++a){
		for(int b = 1; b <= n; ++b){
			if(cap[a][b+n] == flo[a][b+n]){
				maxi = max(maxi, cst[a][b+n]);
			}
		}
	}
	fout << fixed << setprecision(8);
	fout << maxi << " " << total;
}

int main(){
	// ios_base::sync_with_stdio(false);
	read();
	solve();
	write();
	return 0;
}