题解:

二分图最大匹配

建边和第一题差不多

每两个相邻的建边

然后输出方案

代码:

#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=;
int vis[N],a[N][N],ans[N],map[N][N],g[N];
int k,n,m,sum,num;
struct node{int x,y;}p[N*N];
int dfs(int x)
{
for (int i=;i<num;i++)
if (!vis[i]&&a[x][i])
{
vis[i]=;
if (ans[i]==-||dfs(ans[i]))
{
ans[i]=x;
return ;
}
}
return ;
}
void match()
{
sum=;
memset(ans,-,sizeof(ans));
for(int i=;i<num;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i)) sum++;
}
}
int main()
{
while (scanf("%d%d",&n,&m))
{
if (!n&&!m) break;
int u,v;
memset(a,,sizeof(a));
memset(map,,sizeof(map));
scanf("%d",&k);
while (k--)
{
scanf("%d%d",&u,&v);
map[u][v]=;
}
num=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (map[i][j]==)
{
p[num].x=i;
p[num++].y=j;
}
for (int l=;l<num;l++)
for (int j=l+;j<num;j++)
if ((abs(p[l].x-p[j].x)==&&p[l].y==p[j].y)
||(abs(p[l].y-p[j].y)==&&p[l].x==p[j].x))
if ((p[l].x+p[l].y)%==)a[j][l]=;else a[l][j]=;
match();
printf("%d\n",sum);
for (int i=;i<num;i++)
if (ans[i]!=-)
printf("(%d,%d)--(%d,%d)\n",p[i].x,p[i].y,p[ans[i]].x,p[ans[i]].y);
printf("\n");
}
return ;
}

最新文章

  1. Oracle的表锁死以及解锁
  2. jquery改变文本框颜色
  3. Linux进程间通信(七):消息队列 msgget()、msgsend()、msgrcv()、msgctl()
  4. CSS选择器--普通选择器
  5. android开发(49) android 使用 CollapsingToolbarLayout ,可折叠的顶部导航栏
  6. 【BZOJ 3143】【Hnoi2013】游走 期望+高斯消元
  7. Java基础(52):ClassCastException详解(转)
  8. 串行CPU设计
  9. Ajax原理、优缺点及应用场景
  10. linux下的系统垃圾清理
  11. python note 17 random、time、sys、os模块
  12. 爱上linux 简单实现移动办公处理环境.
  13. java第七周动手动脑
  14. CSS 层级选择器
  15. 改变自己从学习linux开始
  16. spark dataframe操作集锦(提取前几行,合并,入库等)
  17. java zxing生成二维码
  18. Shiro - 关于session
  19. c++继承详解:共有(public)继承,私有继承(private)继承,保护(protected)继承
  20. 创建Django与项目介绍

热门文章

  1. google GFS
  2. Eclipse 导入Maven 项目报错
  3. LocalStorage存储JSON对象的问题
  4. web.xml&lt;context-param&gt;与&lt;init-param&gt;的作用与区别
  5. 20145302张薇《Java程序设计》实验五报告
  6. 20145312 实验五 《Java网络编程》
  7. node实现rar格式压缩
  8. PHP中的strtotime()函数
  9. Understanding and Creating OWIN Middlewares - Part 1
  10. IPFS星际节点网站 IPNS域名解析教程