poj2446
2024-08-29 01:19:06
题解:
二分图匹配
看看是否能达到目标
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
int num,ne[N],fi[N],zz[N],k,cnt,a[][],f[N],match[N],x,y,n,m;
void jb(int x,int y)
{
ne[++num]=fi[x];
fi[x]=num;
zz[num]=y;
ne[++num]=fi[y];
fi[y]=num;
zz[num]=x;
}
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 ;
}
int main()
{
while (~scanf("%d%d%d",&m,&n,&k))
{
memset(fi,,sizeof fi);
memset(a,,sizeof a);
memset(match,,sizeof match);
num=cnt=;
for (int i=;i<=k;i++)
{
scanf("%d%d",&x,&y);
a[y][x]=-;
}
if ((n*m-k)%)
{
puts("NO");
continue;
}
for (int i=;i<=m;i++)
for (int j=;j<=n;j++)
if (!a[i][j])a[i][j]=++cnt;
for (int i=;i<=m;i++)
for (int j=;j<=n;j++)
if (a[i][j]!=-)
{
if (a[i+][j]!=-&&i!=m)jb(a[i][j],a[i+][j]);
if (a[i][j+]!=-&&j!=n)jb(a[i][j],a[i][j+]);
}
int ans=;
for (int i=;i<=cnt;i++)
{
memset(f,,sizeof f);
ans+=dfs(i);
}
ans/=;
if (ans*==cnt)puts("YES");
else puts("NO");
}
}
最新文章
- 显示或隐藏div
- OC编程的一些UI细节
- Linux内核分析--操作系统是如何工作的
- javascript宿主对象之window.location
- C/C++学习----使用C语言代替cmd命令、cmd命令大全
- C# BeginInvoke
- python中super关键字的用法
- python(15)提取字符串中的数字
- java android 访问DELPHI 的DATASNAP
- 在Android应用程序使用YouTube API来嵌入视频
- 函数学习(JY07-JavaScript-JS基础03)
- ASP.NET MVC 3 Razor Nested foreach with if statements
- OSS最新进度汇报(2.25)
- .NET中使用Redis总结
- Django项目之小博客
- 201521123080《Java程序设计》第8周学习总结
- Git飞行规则
- JEECG DataGridColumn dictionary使用问题
- Codeforces 660F Bear and Bowling 4 斜率优化 (看题解)
- DELPHI中完成端口(IOCP)的简单分析(4)
热门文章
- LeetCode232:Implement Queue using Stacks
- C#笔试面试宝典值得收藏
- PAT 1126 Eulerian Path[欧拉路][比较]
- mapreduce中获取输入文件的路径
- jmeter+ant+jenkins接口自动环境搭建
- mysql第一天作业
- 在w3cschool学完html,css,javascript,jquery以后,还是不会做前端怎么办?
- List和Set区别
- javaEE中的hibernate配置笔记
- ASP.NET MVC 在项目中使用面包屑导航