Cod sursa(job #48054)

Utilizator TYTUSVlad Saveluc TYTUS Data 4 aprilie 2007 13:04:50
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

vector<pair<double,double> >A,B;
int n,mat[ 401 ][ 401 ];

void read() {
	FILE *fin=fopen ("adapost.in","r");
	fscanf (fin,"%d",&n);
	int i;
	for (i=1;i<=n;++i) {
		double a,b;
		fscanf (fin,"%lf %lf",&a,&b);
		A.push_back( make_pair(a,b) );
	}
	for (i=1;i<=n;++i) {
		double a,b;
		fscanf (fin,"%lf %lf",&a,&b);
		B.push_back( make_pair(a,b) );
	}
}

void build() {
	int i,j;
	for (i=0;i<=n;++i) 
		for (j=0;j<=n;++j) {
			double d=sqrt( (A[i].first-B[j].first)*(A[i].first-B[j].first) + (A[i].second-B[j].second)*(A[i].second-B[j].second) );
			d+=1e-4;
			d*=1000.0;
			mat[ i+1 ][ j+1 ]=d;
			mat[ i+1 ][ j+1 ]=2000000-mat[ i+1 ][ j+1 ];
		}
}

int munkres(int x) {
	int x[ 401 ][ 401 ];
	int i,j;
	//Etapa 1
	for (i=1;i<=n;++i)
		for (j=1;j<=n;++j)
			if (mat[ i ][ j ] < 2000000-x) x[ i ][ j ]=200*1000*1000;
			else x[ i ][ j ]=mat[ i ][ j ];
	for (i=1;i<=n;++i) {
		int min=x[ 1 ][ i ];
		for (j=2;j<=n;++j)
			if (x[ j ][ i ] < min) min=x[ j ][ i ];
		for (j=1;j<=n;++j) x[ j ][ i ]-=min;
	}
	for (i=1;i<=n;++i) {
		int min=x[ i ][ 1 ];
		for (j=2;j<=n;++j) 
			if (x[ i ][ j ] < min) min=x[ i ][ j ];
		for (j=1;j<=n;++j)
			x[ i ][ j ]-=min;
	}
	//Etapa 2
	int nrz[ 401 ],nr=0;
	int pick=1;
	for (i=1;i<=n;++i) {
		nrz[ i ]=0;
		for (j=1;j<=n;++j)
			if (x[ i ][ j ]==0) nrz[ i ]++;
		nr+=nrz[ i ];
	}
	while (nr > 0) {
		int min=n+1,linie;
		for (i=1;i<=n;++i)
			if (nrz[ i ] > 0 && nrz[ i ] < min) {
				min=nrz[ i ];
				linie=i;
			}
		int k;
		for (k=1; x[ linie ][ k ] != 0; ++k);
		x[ linie ][ k ]=-1;
		for (j=k+1; j <=n;++j) if (x[ linie ][ j ]==0) x[ linie ][ j ]=-2;
		nr-=nrz[ linie ];
		nrz[ linie ]=0;
		for (i=1;i<=n;++i)
			if (i!=linie && x[ i ][ k ]==0) {
				x[ i ][ k ]=-2;
				nrz[ i ]--;
				nr--;
			}
	}
		
		
		
		
	
		
		

int main() {
	FILE 
	vector<pair<int,int> >A,B;