Pagini recente » Cod sursa (job #322624) | Cod sursa (job #744301) | Cod sursa (job #1238330) | Cod sursa (job #732822) | Cod sursa (job #48054)
Cod sursa(job #48054)
#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;