POJ 3565 Ants

题目链接http://poj.org/problem?id=3565

题意:平面上有2\times n个点,n个是白点,n个是黑点。对于每个白点,找到一个黑点,把二者用线段连起来,要求最后所有的线段都不相交,求一种方案。

思路:分析可得其实问题最后等价于每条线段的长度之和最小,因为假设平面上两个白点,两个黑点,如果两个连接的线段相交,那么我们交换一下就不会相交,且由三角形两边之和大于第三边可知,两条线段的长度之和一定减小。又因为黑点只与白点相连,我们把白点当作左部的点,黑点当作右部的点,白点和黑点间连一条边权为他们平面上的距离的边然后求二分图带权最小匹配就可以了,匹配边就是我们要求的方案。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100+10;
int n,i,j,k,a[N],b[N],c[N],d[N],match[N],ans[N],va[N],vb[N];
double delta,la[N],lb[N],w[N][N];
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])<1e-10){
            vb[y]=1;
            if(!match[y]||dfs(match[y])){
                match[y]=x; 
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    read(n);
    for (i=1;i<=n;i++) read(a[i]),read(b[i]);
    for (i=1;i<=n;i++) read(c[i]),read(d[i]);
    for (i=1;i<=n;i++) la[i]=-1e12;
    for (i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            w[i][j]=-sqrt(1.0*(a[i]-c[j])*(a[i]-c[j])+1.0*(b[i]-d[j])*(b[i]-d[j]));
            la[i]=max(la[i],w[i][j]);
        }
    }
    for (i=1;i<=n;i++){
        for (;;){
            memset(va,0,sizeof(va));
            memset(vb,0,sizeof(vb));
            delta=1e12;
            if (dfs(i)) break;
            for (j=1;j<=n;j++)if(va[j]){
                for (k=1;k<=n;k++)if(!vb[k]){
                    delta=min(delta,la[j]+lb[k]-w[j][k]);
                }
            }
            for (j=1;j<=n;j++){
                if (va[j]) la[j]-=delta;
                if (vb[j]) lb[j]+=delta;
            }
        }
    }
    for (i=1;i<=n;i++) ans[match[i]]=i;
    for (i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注