记录编号	586254	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[POJ 3565]蚂蚁	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2024-01-10 17:44:46	内存使用	1.31 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 110,M = 2e4+10;
const double eps = 1e-8;
//二分图带权最大匹配
int n;
struct node{
    int x,y;
}a[N],b[N];
int hd[N],tot;
int match[N];
double la[N],lb[N],w[N][N],upd[N],d;
bool va[N],vb[N];
double distan(int x,int y){
    return sqrt((double)(a[x].x-b[y].x)*(a[x].x-b[y].x)+(a[x].y-b[y].y)*(a[x].y-b[y].y));
}
bool dfs(int x){
    va[x] = 1;
    for(int y = 1;y <= n;y++){
        if(!vb[y]){
            if(fabs(la[x] + lb[y] - w[x][y]) < eps){
                vb[y] = 1;
                if(!match[y] || dfs(match[y])){
                    match[y] = x;
                    return 1;
                }
            }
            else upd[y] = min(upd[y],la[x] + lb[y] - w[x][y]);
        }
    }
    return 0;
}
int main(){
    freopen("ant.in","r",stdin);
    freopen("ant.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)scanf("%d%d",&b[i].x,&b[i].y);
	for(int i = 1;i <= n;i++)scanf("%d%d",&a[i].x,&a[i].y);
	for(int i = 1;i <= n;i++){
	    la[i] = INT_MIN;
	    lb[i] = 0;
	    for(int j = 1;j <= n;j++){
	        w[i][j] = -distan(i,j);//将最小匹配改为最大匹配 
	        la[i] = max(la[i],w[i][j]);
        }
    }
    //KM 
	for(int i = 1;i <= n;i++){
	    while(1){
	        memset(va,0,sizeof(va));
	        memset(vb,0,sizeof(vb));
	        d = INT_MAX;
	        for(int j = 1;j <= n;j++)upd[j] = INT_MAX;
	        if(dfs(i))break;
	        for(int j = 1;j <= n;j++)
                if(!vb[j])d = min(d,upd[j]);
	        for(int j = 1;j <= n;j++){
	            if(va[j])la[j] -= d;
	            if(vb[j])lb[j] += d;
            }
        }
    }
    //
    for(int i = 1;i <= n;i++)printf("%d\n",match[i]);
	
	return 0;
	
}