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

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

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;
}