ACM学习历程—POJ3565 Ants(最佳匹配KM算法)

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 n ant colonies and n apple trees. He knows that ants travel from their colony to their feeding places and back using chemically tagged routes. The routes cannot intersect each other or ants will get confused and get to the wrong colony or tree, thus spurring a war between colonies.

Bill would like to connect each ant colony to a single apple tree so that all n routes are non-intersecting straight lines. In this problem such connection is always possible. Your task is to write a program that finds such connection.

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

The first line of the input file contains a single integer number n (1 ≤ n ≤ 100) — the number of ant colonies and apple trees. It is followed by n lines describing n ant colonies, followed by n lines describing n apple trees. Each ant colony and apple tree is described by a pair of integer coordinates x and y (−10 000 ≤ xy ≤ 10 000) on a Cartesian plane. All ant colonies and apple trees occupy distinct points on a plane. No three points are on the same line.

Output

Write to the output file n lines with one integer number on each line. The number written on i-th line denotes the number (from 1 to n) of the apple tree that is connected to the i-th ant colony.

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

题目就是求类似图中实心到空心圆的连线,一一映射,使两两线段不相交。

有一种思路就是一开始让所有点对随意连接,然后让相交的线段进行调整,这里比较好理解,比如AC与BD相交,那么AD与BC就必然不相交了。这样的话需要的调整的次数似乎不是很好计算。

但是可以肯定的是,最终状态必然是两两不相交了。

可以发现上面相交的AC与BD,必然满足AD+BC < AC+BD。这里可以用两次三角形两边之和大于第三边进行证明。这一步让点对里面边的权值和变小了。

于是考虑,逆命题:是否当边AC与BD可以减小成AD与BC时,一定是相交的?

事实证明这个命题是不一定的,但是可以发现当可以减小成AD与BC时,AD和BC一定是不相交的。否则会导致AD+BC > AC+BD。

所以只要能减小边权的和,一定能保证不相交。那么最终状态就变成了边权和最小的状态,也就是最小匹配。可以采用KM算法进行。

似乎是数据问题,不能使用边的平方进行处理。要用double保存边的大小,然后等于0的判断,改成小于eps。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long

using namespace std;

const int maxN = 105;
const double inf = 1e10;
int n;
struct Point
{
    double x, y;
}x[maxN], y[maxN];
int nx, ny;
int link[maxN];
double lx[maxN], ly[maxN], slack[maxN], w[maxN][maxN];//link表示和y相接的x值,lx,ly为顶标,nx,ny分别为x点集y点集的个数
bool visx[maxN], visy[maxN];

inline double dis(int i, int j)
{
    double ans = (x[i].x-y[j].x)*(x[i].x-y[j].x) + (x[i].y-y[j].y)*(x[i].y-y[j].y);
    return -sqrt(ans);
}

bool DFS(int x)
{
    visx[x] = true;
    for (int y = 1; y <= ny; y++)
    {
        if (visy[y])
            continue;
        double t = lx[x]+ly[y]-w[x][y];
        if (fabs(t) < 1e-5)
        {
            visy[y] = true;
            if (link[y] == -1 || DFS(link[y]))
            {
                link[y] = x;
                return true;
            }
        }
        else if (slack[y] > t)//不在相等子图中slack取最小的
            slack[y] = t;
    }
    return false;
}

void KM()
{
    memset(link, -1, sizeof(link));
    memset(ly, 0, sizeof(ly));
    for (int i = 1; i <= nx; i++)//lx初始化为与它关联边中最大的
        for (int j = 1; j <= ny; j++)
            if (j == 1 || w[i][j] > lx[i])
                lx[i] = w[i][j];

    for (int x = 1; x <= nx; x++)
    {
        for (int i = 1; i <= ny; i++)
            slack[i] = inf;
        for (;;)
        {
            memset(visx, false, sizeof(visx));
            memset(visy, false, sizeof(visy));
            if (DFS(x))//若成功(找到了增广轨),则该点增广完成,进入下一个点的增广
                break;//若失败(没有找到增广轨),则需要改变一些点的标号,使得图中可行边的数量增加。
                    //方法为:将所有在增广轨中(就是在增广过程中遍历到)的X方点的标号全部减去一个常数d,
                    //所有在增广轨中的Y方点的标号全部加上一个常数d
            double d = inf;
            for (int i = 1; i <= ny; i++)
                if (!visy[i] && d > slack[i])
                    d = slack[i];
            for (int i = 1; i <= nx; i++)
                if (visx[i])
                    lx[i] -= d;
            for (int i = 1; i <= ny; i++)//修改顶标后,要把所有不在交错树中的Y顶点的slack值都减去d
                if (visy[i])
                    ly[i] += d;
                else
                    slack[i] -= d;
        }
    }

    for (int i = 1; i <= n; ++i)
        printf("%d\n", link[i]);
}

void input()
{
    nx = ny = n;
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &y[i].x, &y[i].y);
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &x[i].x, &x[i].y);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            w[i][j] = dis(i, j);
}

int main ()
{
    //freopen("test.in", "r", stdin);
    while (scanf ("%d", &n) != EOF)
    {
        input();
        KM();
    }
    return 0;
}
时间: 10-05

ACM学习历程—POJ3565 Ants(最佳匹配KM算法)的相关文章

hdu2255 奔小康赚大钱 二分图最佳匹配--KM算法

传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子.这可是一件大事,关系到人民的住房问题啊.村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子.另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(

ACM学习历程—HDU 4726 Kia&#39;s Calculation( 贪心&amp;&amp;计数排序)

DescriptionDoctor Ghee is teaching Kia how to calculate the sum of two integers. But Kia is so careless and alway forget to carry a number when the sum of two digits exceeds 9. For example, when she calculates 4567+5789, she will get 9246, and for 12

ACM学习历程—HDU 5023 A Corrupt Mayor&#39;s Performance Art(广州赛区网赛)(线段树)

Problem Description Corrupt governors always find ways to get dirty money. Paint something, then sell the worthless painting at a high price to someone who wants to bribe him/her on an auction, this seemed a safe way for mayor X to make money. Becaus

LA4043 - Ants(二分图完备最佳匹配KM)

option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044 大致题意: 平面上有n个白点和n个黑点,求一种完美匹配使他们间的连线不相交 思路:要注意到,若有两种匹

ACM学习历程—HDU 5536 Chip Factory(xor &amp;&amp; 字典树)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5536 题目大意是给了一个序列,求(si+sj)^sk的最大值. 首先n有1000,暴力理论上是不行的. 此外题目中说大数据只有10组,小数据最多n只有100.(那么c*n^2的复杂度应该差不多) 于是可以考虑枚举i和j,然后匹配k. 于是可以先把所有s[k]全部存进一个字典树, 然后枚举s[i]和s[j],由于i.j.k互不相等,于是先从字典树里面删掉s[i]和s[j],然后对s[i]+s[j]这个

ACM学习历程——ZOJ 3829 Known Notation (2014牡丹江区域赛K题)(策略,栈)

Description Do you know reverse Polish notation (RPN)? It is a known notation in the area of mathematics and computer science. It is also known as postfix notation since every operator in an expression follows all of its operands. Bob is a student in

ACM学习历程—BestCoder Round #75

1001:King's Cake(数论) http://acm.hdu.edu.cn/showproblem.php?pid=5640 这题有点辗转相除的意思.基本没有什么坑点. 代码: #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include &l

ACM学习历程—HDU5585 Numbers(数论 || 大数)(BestCoder Round #64 (div.2) 1001)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5585 题目大意就是求大数是否能被2,3,5整除. 我直接上了Java大数,不过可以对末尾来判断2和5,对所有位的和来判断3. 代码就不粘了.

ACM学习历程—HDU5587 Array(数学 &amp;&amp; 二分 &amp;&amp; 记忆化 || 数位DP)(BestCoder Round #64 (div.2) 1003)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5587 题目大意就是初始有一个1,然后每次操作都是先在序列后面添加一个0,然后把原序列添加到0后面,然后从0到末尾,每一个都加上1. 例如:a0, a1, a2 => a0, a1, a2, 1, a0+1, a1+1, a2+1 题解中是这么说的:“ 其实Ai为i二进制中1的个数.每次变化A{k+2^i}=A{k}+1,(k<2^?i??)不产生进位,二进制1的个数加1.然后数位dp统计前m个数二