Punching Power Gym - 101670J

接触匈牙利算法的第一个实际应用题

题目链接

匈牙利算法大家可以自己百度，讲的很好生动形象

这道题是二分图匹配的一道实际应用，要求求最大点的集合，集合中任意两点距离必须大于1.3

因此我们可以反过来求两点相连距离为1（因为所给点的坐标都是整数），求出最大匹配后，点数 - 最大匹配数就是二分图的最大独立点集。那既然是二分图，我们该如何把n个点，分成两部分呢？很明显（一点都不明显好嘛！），在一部分的所有点任意两点距离都得大于1，如果两点x + y的奇偶性相同，那么这两个点距离一定大于一。所以这n个点，x + y的和都为奇数的在一部分，剩下的就是另一部分了。

AC代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2018;
int use[maxn],match[maxn];
struct node
{
    int x,y;
    bool operator < (const node & p)const
    {
        return x + y > p.x + p.y;
    }
}a[maxn];
vector<int> edges[maxn];
bool found(int p)
{
    for(int i = 0;i < (int)edges[p].size();i++)
    {
        int e = edges[p][i];
        if(!use[e])
        {
            use[e] = 1;
            if(!match[e] || found(match[e]))
            {
                match[e] = p;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        memset(a,0,sizeof(a));
        memset(match,0,sizeof(match));
        for(int i = 1;i <= n;i++)
        {
            edges[i].clear();
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        sort(a + 1,a + n + 1);
        for(int i = 1;i <= n;i++)
        {
            for(int j = i + 1;j <= n;j++)
            {
                if((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y) == 1)
                {
                    //printf("%d %d\n",i,j);
                    edges[i].push_back(j);
                    edges[j].push_back(i);
                }
            }
        }
        int ans = 0;
        for(int i = 1;i <= n;i++)
        {
            memset(use,0,sizeof(use));
            if((a[i].x + a[i].y) % 2)
            {
                if(found(i)) ans++;
            }
        }
        printf("%d\n",n - ans);
    }
    return 0;
}