题目是跟 zoj1516是一样的,但多了匹配后的输出

详解zoj1516可见http://www.cnblogs.com/CSU3901130321/p/4228057.html

 #include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; const int maxn = ;
int n , m , k;
int g[maxn][maxn] , cx[maxn] , cy[maxn] , visy[maxn] , nx , ny;
bool col[][];//判断是否为鱼塘 struct Point{
int x , y;
Point(int x= , int y=):x(x),y(y){}
}; Point px[maxn] , py[maxn]; bool ok(Point p1 , Point p2)
{
if((p1.x == p2.x && abs(p1.y - p2.y) == ) || (p1.y == p2.y && abs(p1.x - p2.x) == ))
return true;
return false;
} void build_graph()
{
memset(g , , sizeof(g));
for(int i= ; i<=nx ; i++){
for(int j= ; j<=ny ; j++){
if(ok(px[i] , py[j]))
g[i][j] = ;
}
}
} int dfs(int u)
{
for(int v = ; v<=ny ; v++)
if(g[u][v] && !visy[v]){
visy[v] = ;
if(cy[v] == - || dfs(cy[v])){
cx[u] = v;
cy[v] = u;
return ;
}
}
return ;
} int MaxMatch()
{
memset(cx , - , sizeof(cx));
memset(cy , - , sizeof(cy));
int ans = ;
for(int i= ; i<=nx ; i++){
if(cx[i] == -){
memset(visy , , sizeof(visy));
ans += dfs(i);
}
}
return ans;
} int main()
{
// freopen("a.in" , "r" ,stdin);
while(scanf("%d%d" , &n , &m) , n)
{
scanf("%d" , &k);
int x , y;
memset(col , , sizeof(col));
while(k--){
scanf("%d%d" , &x , &y);
col[x][y] = ;
}
nx = , ny = ;
for(int i= ; i<=n ; i++)
for(int j= ; j<=m ; j++)
if(!col[i][j]){
if((i+j)&) py[++ny] = Point(i,j);
else px[++nx] = Point(i,j);
}
//构造二分图
build_graph();
printf("%d\n" , MaxMatch());
for(int i= ; i<=nx ; i++){
if(cx[i] != -)
printf("(%d,%d)--(%d,%d)\n",px[i].x , px[i].y , py[cx[i]].x , py[cx[i]].y);
}
}
return ;
}

最新文章

  1. 设置DataSource后DateGridView不显示的问题
  2. Python requests 为pfsense 添加Routes
  3. 使用MVC过滤器保存操作日志
  4. css——手机端图片正确显示
  5. 桂电在linux环境下使用出校器
  6. 我的ubuntu配置
  7. [置顶] UITableViewCell
  8. 来推荐个免费的PPT演示工具--ZohoShowTime
  9. Cocos2d-x 3.2 Lua演示样本CocosDenshionTest(音频测试)
  10. 原生JS-----论数据类型检测
  11. Unity与iOS原生代码之间的相互调用
  12. Netty入门之HelloWorld
  13. assert后面如果是假则程序崩溃
  14. 对oracle数据库的数据迁移
  15. 51行代码实现简单的PHP区块链
  16. MS SQL批量生成作业脚本方法介绍总结
  17. 【BZOJ3997】【TJOI2015】组合数学 Dilworth定理 DP
  18. 【POJ3017】Cut the Sequence
  19. [No000018B]写代码要用 Vim,因为越难入门的工具回报越大
  20. MongoDB--预备

热门文章

  1. bzoj 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛【dp+树状数组+hash】
  2. 10.17NOIP模拟赛
  3. 乐搏讲自动化测试-Python语言常识及前景(3)
  4. 全面学习ORACLE Scheduler特性(1)创建jobs
  5. NPOI 导出excel数据超65535自动分表
  6. java list遍历三种方法
  7. ES6 学习笔记 - let和const
  8. reduce的特殊用法
  9. Android 知识Tips
  10. vue+vux+es6+webpack移动端常用配置步骤