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