题目:

The park management finally decided to install some popular boxing machines at various strategic places in the park. In fact, to compensate for the previous lack of machines, they decided to install as many machines as possible. Surprisingly enough, the park is not going to be choked with new machines because there are some quite serious legal limitations regarding the locations of the machines. The management has marked all possible boxing machine locations and their respective coordinates on the park plan. Additionally, they also have to respect manufacturer security rule: The distance between any two boxing machines has to be at least 1.3 meters.

Help the management to establish the maximum possible number of boxing machines which can be installed in the park.

Input Specification:

There are several test cases. Each case starts with a line containing one integer N which specifies the number of possible boxing machine locations in the park (1 ≤ N ≤ 2000). Next, there are N lines representing the location coordinates, each line describes one location by a pair of integer coordinates in meters. All locations in one test case are unique. Each coordinate is non-negative and less than or equal to 109 .

You are guaranteed that all locations form a single connected group, that is, it is possible to start in any location and reach any other location by a sequence of steps, each of which changes exactly one coordinate by 1, without leaving the area suitable for placing boxing machines.

Output Specification:

For each test case, print a single line with one integer representing the maximum number of boxing machines which can be installed in the park.

思路:

反向来解决这道题目,先对不符合条件的点建图,求这个图的二分匹配。

建图的规则是水平竖直相邻的,距离是1,不符合题意,其他的距离肯定是大于1.3米的,直接自闭。

首先建好图,然后求最大独立集就ok了,最大独立集 = 点的个数 - 最大匹配数。

总结这道题被卡的原因:

对匈牙利算法的理解太浅显!

读题不精!

代码:

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = ;
struct Node
{
int x,y;
} node[maxn];
vector<int>v[maxn];
int n,vis[maxn],linker[maxn]; bool dfs(int u)
{
for(int i = ; i<v[u].size(); i++)//每个与u相连的点
{
int _v = v[u][i];//放进交替路中
if(!vis[_v])
{
vis[_v] = ;
if(linker[_v]== || dfs(linker[_v]))//是未匹配点,说明该交替路是增广路径,交换路径
{
linker[_v] = u;
linker[u] = _v;
return true;
}
}
}
return false;
} int match()
{
int res = ;
memset(linker,,sizeof(linker));
for(int i = ; i<n; i++)
{
memset(vis,,sizeof(vis));
if(linker[i]== && dfs(i))
res++;
}
return res;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i = ; i<=n; i++)
{
scanf("%d%d",&node[i].x,&node[i].y);
}
for(int i = ; i<=n; i++)
{
v[i].clear();
for(int j = ; j<=n; j++)
{
if(abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y)==)
{
v[i].push_back(j);
}
}
}
int ans = match();
//cout<<"ans: "<<ans<<endl;
printf("%d\n",n-ans);
}
return ;
}

最新文章

  1. ECMAScript5 Array新增方法
  2. Eclipse统计代码行数
  3. 关于listview排序的说明
  4. virtual box 中两个虚拟机 、宿主机 三机互通并且能上外网设置
  5. js 正则表达式 手机号
  6. VMware系统运维(二)安装Microsoft .NET 3.5
  7. Codeforces 484A - Bits 二进制找1
  8. canvas入门之时钟的实现
  9. [坑]Spring利用注解@Value获取properties属性为null
  10. ArrayDataProvider数据分页
  11. 应用程序池--IIS最大工作进程数
  12. 《Java Concurrency》读书笔记,使用JDK并发包构建程序
  13. php实现cookie加密解密
  14. Mac 切换到行首和行末的方法
  15. Linux下Nginx+多Tocat下的负载均衡环境的简单搭建
  16. 2018-2019-1 20189215 《Linux内核原理与分析》第九周作业
  17. HDU 5389 Zero Escape(dp啊 多校)
  18. C# Winform 使用Application.Exit重新启动应用程序example
  19. scheme 中的宏使用
  20. SVN脱离锁定的几种方法

热门文章

  1. Maven环境配置及命令行打包
  2. COCI2012 TOY
  3. 2-3 原生小程序 - 项目app.json配置
  4. 7章 Admin
  5. E20170609-ts
  6. poj 2154 Color【polya定理+欧拉函数】
  7. php使用邮箱发送验证码
  8. xposed源码编译与集成
  9. Oracle随机选择一条记录SQL
  10. DHTML_____如何编写事件处理程序