欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[poj3565] Ants (二分图带权匹配)

程序员文章站 2024-03-17 15:26:52
...

传送门

Description

年轻自然主义者比尔在学校研究蚂蚁。 他的蚂蚁以苹果树上苹果为食。 每个蚁群都需要自己的苹果树来养活自己。
比尔有一张坐标为 n 个蚁群和 n 棵苹果树的地图。 他知道蚂蚁会从他们的巢穴到达他们的喂食地点,并使用化学标记的路线返回。这些路线不能相互交叉,不然蚂蚁会感到困惑,并进入错误的巢穴或苹果树,从而引起蚁群之间的战争。
比尔希望将每个蚁群连接到一棵苹果树上,这样所有n个路径都是非相交的直线。 在这个问题中,这样的连接方式总是存在的。 你的任务是编写一个找到这样的连接方式的程序。

[poj3565] Ants (二分图带权匹配)

在这张照片上,蚁群用空心圆圈表示,苹果树用实心圆圈表示。 这是一条可能的连接方法示意。

Input

输入文件的第一行包含一个整数 n (1≤n≤100 ) - 蚁群和苹果树的数量。 之后是描述n个蚁群的n行,之后是描述n棵苹果树的n行。 每个蚁群和苹果树由笛卡尔平面上的一对整数坐标 x 和 y (−10000≤x,y≤10000 )描述。 所有蚂蚁巢穴和苹果树在地图上占据不同的点。 没有三点是在同一条线上。

Output

输出n行,每行有一个整数。 写在第i行上的数字表示连接到第i个蚁群的苹果树的编号(从1到n)。

Sample Input

5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60

Sample Output

4
2
1
5
3

Solution

Km模板

Code

//By Menteur_Hxy
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
using namespace std;

int read() {
    int x=0,f=1; char c=getchar();
    while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
    return x*f;
}

const int N=128,INF=0x3f3f3f3f;
int n;
int mat[N],va[N],vb[N];
double tmp;
double la[N],lb[N],dis[N][N];
struct Poi{double x,y;}T[N],A[N];

bool dfs(int u) {
    va[u]=1;
    F(v,1,n) if(!vb[v]) 
        if(la[u]+lb[v]-dis[u][v]<1e-6) {
            vb[v]=1;
            if(!mat[v] || dfs(mat[v])) {mat[v]=u;return 1;}
        }
    return 0;
}

void KM() {
    F(i,1,n) {
        la[i]=-INF,mat[i]=lb[i]=0;
        F(j,1,n) la[i]=max(la[i],dis[i][j]);
    }
    F(i,1,n) {
        while(1) {
            memset(va,0,sizeof(va));
            memset(vb,0,sizeof(vb));
            // cout<<i<<endl;
            if(dfs(i)) break;
            tmp=INF;
            F(j,1,n) if(va[j]) F(k,1,n) if(!vb[k]) 
                tmp=min(tmp,la[j]+lb[k]-dis[j][k]);
            // cout<<tmp<<endl;
            // F(j,1,n) cout<<la[j]<<" ";cout<<endl;
            // F(j,1,n) cout<<lb[j]<<" ";cout<<endl;
            F(j,1,n) {
                if(va[j]) la[j]-=tmp;
                if(vb[j]) lb[j]+=tmp;
            }
        }
    }
}

int main() {
    // freopen("read.txt","r",stdin);
    // freopen("1.txt","w",stdout);
    while(~scanf("%d",&n)) {
        F(i,1,n) T[i].x=read(),T[i].y=read();
        F(i,1,n) A[i].x=read(),A[i].y=read();
        F(i,1,n) F(j,1,n) dis[i][j]=-sqrt((A[i].x-T[j].x)*(A[i].x-T[j].x)+(A[i].y-T[j].y)*(A[i].y-T[j].y));
        KM();
        F(i,1,n) printf("%d\n",mat[i]);
    }
    return 0;
}
相关标签: 二分图