poj 题目3041 Asteroids （最小点覆盖）

不念不忘少年蓝@ 2022-12-22 02:25 122阅读 0赞

[http://poj.org/problem?id=3041][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

首先,我们利用行跟列做二分图:

![20130903125847968][]

**如果第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;
    }

[http_poj.org_problem_id_3041]: http://poj.org/problem?id=3041
[20130903125847968]: /images/20221120/1bb15731dea44d1783ca092221e55edc.png