大意略。
二分图最佳匹配,KM算法。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <map> using namespace std; const int maxn = 110; const int INF = 0x3f3f3f3f; const double eps = 1e-7; struct node { double x, y; node(double x=0, double y=0): x(x), y(y) {} }A[maxn], B[maxn]; double sqr(double x) { return x*x; } double dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0? -1:1; } double Dist(node a, node b) { return sqrt(sqr(a.x-b.x) + sqr(a.y-b.y)); } int n; double W[maxn][maxn]; double Lx[maxn], Ly[maxn]; int Left[maxn]; bool S[maxn], T[maxn]; bool match(int i) { S[i] = 1; for(int j = 1; j <= n; j++) if(!dcmp(Lx[i]+Ly[j]-W[i][j])&& !T[j]) { T[j] = 1; if(!Left[j] || match(Left[j])) { Left[j] = i; return 1; } } return 0; } void update() { double a = INF; for(int i = 1; i <= n; i++) if(S[i]) for(int j = 1; j <= n; j++) if(!T[j]) a = min(a, Lx[i]+Ly[j]-W[i][j]); for(int i = 1; i <= n; i++) { if(S[i]) Lx[i] -= a; if(T[i]) Ly[i] += a; } } void KM() { for(int i = 1; i <= n; i++) { Left[i] = Lx[i] = Ly[i] = 0; for(int j = 1; j <= n; j++) Lx[i] = max(Lx[i], W[i][j]); } for(int i = 1; i <= n; i++) { for(;;) { for(int j = 1; j <= n; j++) S[j] = T[j] = 0; if(match(i)) break; else update(); } } } void read_case() { for(int i = 1; i <= n; i++) { double x, y; scanf("%lf%lf", &x, &y); A[i] = node(x, y); } for(int i = 1; i <= n; i++) { double x, y; scanf("%lf%lf", &x, &y); B[i] = node(x, y); } } void build() { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { W[j][i] = -Dist(A[i], B[j]); } } void solve() { read_case(); build(); KM(); for(int i = 1; i <= n; i++) printf("%d\n", Left[i]); } int main() { int times = 0; while(~scanf("%d", &n)) { if(++times > 1) printf("\n"); solve(); } return 0; }