题解:

二分图匹配

看看是否能达到目标

代码:

#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");
}
}

最新文章

  1. 显示或隐藏div
  2. OC编程的一些UI细节
  3. Linux内核分析--操作系统是如何工作的
  4. javascript宿主对象之window.location
  5. C/C++学习----使用C语言代替cmd命令、cmd命令大全
  6. C# BeginInvoke
  7. python中super关键字的用法
  8. python(15)提取字符串中的数字
  9. java android 访问DELPHI 的DATASNAP
  10. 在Android应用程序使用YouTube API来嵌入视频
  11. 函数学习(JY07-JavaScript-JS基础03)
  12. ASP.NET MVC 3 Razor Nested foreach with if statements
  13. OSS最新进度汇报(2.25)
  14. .NET中使用Redis总结
  15. Django项目之小博客
  16. 201521123080《Java程序设计》第8周学习总结
  17. Git飞行规则
  18. JEECG DataGridColumn dictionary使用问题
  19. Codeforces 660F Bear and Bowling 4 斜率优化 (看题解)
  20. DELPHI中完成端口(IOCP)的简单分析(4)

热门文章

  1. LeetCode232:Implement Queue using Stacks
  2. C#笔试面试宝典值得收藏
  3. PAT 1126 Eulerian Path[欧拉路][比较]
  4. mapreduce中获取输入文件的路径
  5. jmeter+ant+jenkins接口自动环境搭建
  6. mysql第一天作业
  7. 在w3cschool学完html,css,javascript,jquery以后,还是不会做前端怎么办?
  8. List和Set区别
  9. javaEE中的hibernate配置笔记
  10. ASP.NET MVC 在项目中使用面包屑导航