Poj 3041 Asteroids + Poj 2226 Muddy Fields(二分图与一类选方格题目)

秒速五厘米 2021-11-22 21:01 277阅读 0赞

**Poj 3041 Asteroids**

思路：把方阵看做一个特殊的二分图（以行列分别作为两个顶点集V1、V2，其中| V1|=| V2|）  
然后把每行x或者每列y看成一个点，而障碍物(x,y)可以看做连接x和y的边。按照这种思路构图后。问题就转化成为选择最少的一些点(x或y)，使得从这些点与所有的边相邻，其实这就是最小点覆盖问题。.

#include <cstdio>
    #include <cstring>
    
    const int N=505;
    bool map[N][N];
    bool vis[N];
    int match[N];
    
    int n,k;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=n;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==0 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    int main ()
    {
    	int i,temp1,temp2,sum;
    	scanf("%d%d",&n,&k);
    	memset(map,false,sizeof(map));
    	memset(match,0,sizeof(match));
    	for (i=1;i<=k;i++)
    	{
    		scanf("%d%d",&temp1,&temp2);
    		map[temp1][temp2]=true;
    	}
    	for (sum=0,i=1;i<=n;i++)
    	{
    		memset(vis,false,sizeof(vis));
    		if (Dfs(i))
    			sum++;
    	}
    	printf("%d\n",sum);
    	return 0;
    }

**Poj 2226 Muddy Fields**

题意：给定一个矩阵，其中有一些地方有水，用一些长度任意，宽度为1长度不限的木板盖住这些有水的地方，问至少需要几块板子。  
思路：二分图最小点集覆盖。  
二分图建图方法如下：横行的连续\*作为X集合里的顶点，纵行的连续\*作为Y集合的顶点。  
若X和Y集合中的顶点在原图中有相交，则这两个顶点连一条边。

#include <cstdio>
    #include <cstring>
    
    const int N=1000;
    char graph[55][55];
    bool map[N][N];
    bool vis[N];
    int match[N],a[N][N],b[N][N];
    int R,C,x=1,y=1;
    
    bool DFS (int u)
    {
    	for (int v=1;v<=y;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==0 || DFS(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    int main ()
    {
    	int i,j,ans=0;
    	scanf("%d%d",&R,&C);
    	for (i=1;i<=R;i++)
    		scanf("%s",graph[i]+1);
    	memset(a,0,sizeof(a));
    	memset(b,0,sizeof(b));
    	memset(map,false,sizeof(map));
    	memset(match,0,sizeof(match));
    	for (i=1;i<=R;i++)    //扫连续横
    		for (j=1;j<=C;j++)
    			if (graph[i][j]=='*')
    			{
    				a[i][j]=x;
    				x+=(graph[i][j+1]!='*');
    			}
    	for (i=1;i<=C;i++)   //扫连续纵
    		for (j=1;j<=R;j++)
    			if (graph[j][i]=='*')   //注意横纵坐标
    			{
    				b[j][i]=y;
    				y+=(graph[j+1][i]!='*');
    			}
    	for (i=1;i<=R;i++)
    		for (j=1;j<=C;j++)
    			if (graph[i][j] == '*')
    				map[a[i][j]][b[i][j]]=true;
    	for (i=1;i<=x;i++)
    	{
    		memset(vis,false,sizeof(vis));
    		if (DFS(i))
    			ans++;
    	}
    	printf("%d\n",ans);
    	return 0;
    }