本文主要是介绍poj 题目3041 Asteroids （最小点覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=3041
最小覆盖： 最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。
可以证明：最少的点（即覆盖数）＝最大匹配数 M
简单的证明如下：
（1）M个是足够的。只需要让它们覆盖最大匹配的M条边，则其它边一定被覆盖（如果有边e不被覆盖，把e加入后得到一个更大的匹配）
（2）M个是必需的，仅考虑形成最大匹配的这M条边，由于它们两两之间没有公共点，因此至少需要M个点才可以把它们覆盖
题意：
问题:
假如你现在正处在一个N*N的矩阵中,这个矩阵里面有K个障碍物,你拥有一把武器,一发弹药一次能消灭一行或一列的障碍物,求最小的弹药消灭全部障碍物
输入为:
N K
接下来有K行,每行包含障碍物的坐标,即r行c列;
如:
3 4
1 1
1 3
2 2
3 2
输出为:
花费最小的弹药数
分析：
对于上面那个数据我们可以用下面的表示,0表示无障碍物,1表示有;
1 0 1
0 1 0
0 1 0
首先,我们利用行跟列做二分图:
如果第i行的第j列有障碍物,则在图中左边的i行连一条边到右边的j列,上面的数据就对应上图
于是问题就转化成最小点覆盖的问题.求最大匹配即可.
/***************************
# 2013-9-3 12:54:22
# Time: 16MS Memory: 960K
# Author: zyh
# Status: Accepted
***************************/ #include<stdio.h>
#include<string.h>int G[505][505],link[505];
bool vis[505];
int n;bool dfs(int x){for(int i=1;i<=n;i++){if(G[x][i]&&!vis[i]){vis[i] = 1;if(link[i]==-1 || dfs(link[i])){link[i] = x;return 1;}}}return 0;
}
int main()
{int i,k,sum,x,y;scanf("%d%d",&n,&k);
// memset(G,0,sizeof(G)); 一组测试的话，这里不用清零了 memset(link,-1,sizeof(link));while(k--){scanf("%d%d",&x,&y);G[x][y] = 1;}for(sum=0,i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i)) sum++;}printf("%d\n",sum);return 0;
}
这篇关于poj 题目3041 Asteroids （最小点覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
