Uva 1411 - Ants（KM模板O(n^4)）最大权匹配
连接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=560&problem=4157&mosmsg=Submission+received+with+ID+11685541
?
Young naturalist Bill studies ants in school. His ants feed on plant-louses that live on apple trees. Each ant colony needs its own apple tree to feed itself.
Bill has a map with coordinates of?<tex2html_verbatim_mark>
On this picture ant colonies are denoted by empty circles and apple trees are denoted by filled circles. One possible connection is denoted by lines.
?
Input has several dataset. The first line of each dataset contains a single integer number?n
100)?<tex2html_verbatim_mark>-- the number of ant colonies and apple trees. It is followed by?x,?y10000)?<tex2html_verbatim_mark>on a Cartesian plane. All ant colonies and apple trees occupy distinct points on a plane. No three points are on the same line.
?
For each dataset, write to the output file?#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int maxn = 100 + 10;const double INF = 1e30;int n;double W[maxn][maxn];double Lx[maxn], Ly[maxn]; // 顶标int left[maxn]; // left[i]为右边第i个点的匹配点编号bool S[maxn], T[maxn]; // S[i]和T[i]为左/右第i个点是否已标记bool eq(double a, double b) { return fabs(a-b) < 1e-9;}bool match(int i){ S[i] = true; for(int j = 1; j <= n; j++) if (eq(Lx[i]+Ly[j], W[i][j]) && !T[j]){ T[j] = true; if (!left[j] || match(left[j])){ left[j] = i; return true; } } return false;}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(); } }}int main(){ int kase = 0; while(scanf("%d", &n) == 1) { if(++kase > 1) printf("\n"); int x1[maxn], y1[maxn], x2[maxn], y2[maxn]; for(int i = 1; i <= n; i++) scanf("%d%d", &x1[i], &y1[i]); for(int i = 1; i <= n; i++) scanf("%d%d", &x2[i], &y2[i]); for(int i = 1; i <= n; i++) // ant colony for(int j = 1; j <= n; j++) //存成负数找最大值，相当于找最小值 W[j][i] = -sqrt((double)(x1[i]-x2[j])*(x1[i]-x2[j]) + (double)(y1[i]-y2[j])*(y1[i]-y2[j])); KM(); // 最大权匹配 for(int i = 1; i <= n; i++) printf("%d\n", left[i]);//x1[i]这个蚂蚁与x2[left[i]]这个蚂蚁匹配} return 0;}
?
?
?
?
?
?
?
?
?
