题解:

最大独立集问题

显然对于每一对交叉的建边

然后求出最大独立集

最大独立集=n-最大匹配

代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=;
int x[N],f[N],match[N],y[N],fi[N],num,ne[N],zz[N],n,m;
int dfs(int x)
{
for (int i=fi[x];i;i=ne[i])
if (!f[zz[i]])
{
f[zz[i]]=;
if (!match[zz[i]]||dfs(match[zz[i]]))
{
match[zz[i]]=x;
return ;
}
}
return ;
}
void jb(int x,int y)
{
ne[++num]=fi[x];
fi[x]=num;
zz[num]=y;
}
int main()
{
while (~scanf("%d%d",&n,&m),n||m)
{
memset(fi,,sizeof fi);
memset(match,,sizeof match);
num=;
for (int i=;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
for (int i=;i<=m;i++)scanf("%d%d",&x[i+n],&y[i+n]);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (x[i]==x[j+n]&&(y[i]==y[j+n]||y[i]==y[j+n]+)||
x[i]+==x[j+n]&&(y[i]==y[j+n]||y[i]==y[j+n]+))jb(i,j);
int ans=;
for (int i=;i<=n;i++)
{
memset(f,,sizeof f);
ans+=dfs(i);
}
printf("%d\n",n+m-ans);
}
return ;
}

最新文章

  1. BZOJ 1176 [Balkan2007]Mokia ——CDQ分治
  2. 。tar.gz(bz或bz2等)安装
  3. CMT learning
  4. HDU-2296 Ring(AC自动机+DP)
  5. BZOJ 2049 [Sdoi2008]Cave 洞穴勘测 ——Link-Cut Tree
  6. Linux 下 Shell 命令的分类及用法
  7. 随心所欲导出你的 UI 界面到 PDF 文件
  8. 小希的迷宫(MST单棵树判断法则)
  9. 使用ContentProvider管理联系人------搜索联系人
  10. 【Winform】Winform 制作一键发布web
  11. 关于贴友的一个书本页面简单布局(html+css)的实现
  12. mvn详解
  13. [Angular 2] ng-model and ng-for with Select and Option elements
  14. Jedis实现发布订阅功能
  15. 基于Sublime Text搭建Python IDE
  16. C++模板学习:函数模板、结构体模板、类模板
  17. 自制PHP高防防盗链(不是一般的高)(思路)
  18. Elasticsearch教程-从入门到精通(转载)
  19. RCTF 2018线上赛 writeup
  20. python对 if __name__==&#39;__main__&#39;的理解

热门文章

  1. tomcat 是如何处理jsp和servlet请求
  2. make编译五
  3. Linux学习笔记(3)linux服务管理与启停
  4. R语言操作mysql上亿数据量(ff包ffbase包和ETLUtils包)
  5. appium 自动化测试案例
  6. vue之 node.js 的简单介绍
  7. 转:oracle物化视图学习笔记
  8. OpenCL 学习step by step (5) 使用二维NDRange workgroup
  9. Spring 之混合配置
  10. Django学习笔记之使用 Django项目开发框架