poj 2226 还是最小点覆盖的匹配问题

左手的ㄟ右手 2021-11-29 17:42 324阅读 0赞

这题比3041要有点难度，主要是在判断节点的时候，要两次扫描输入的矩阵。这个叫我shi也想不到啊。。人家discuss里面给了很好的模板，学着点吧。具体的分析请看下面:

转自：[http://www.cppblog.com/abilitytao/archive/2009/10/21/99124.aspx][http_www.cppblog.com_abilitytao_archive_2009_10_21_99124.aspx]

Sample:  
4 4  
\*.\*.  
.\*\*\*  
\*\*\*.  
..\*.

把行里面连在一起的坑连起来视为一个点，即一块横木板，编上序号，Sample则转化为：

1 0 2 0  
0 3 3 3  
4 4 4 0  
0 0 5 0

把这些序号加入X集合，再按列做一次则为：

1 0 4 0  
0 3 4 5  
2 3 4 0  
0 0 4 0

同样加入Y集合，一个坑只能被横着的或者被竖着的木板盖住，将原图的坑的也标上不同的序号，一共九个坑

1 . 2 .  
. 3 4 5  
67 8 .  
. . 9 .

比如7号坑可以被横着的4号木板和竖着的3号木板盖住，把每个点的对应的横木板(4)和竖木板(3)中间连一条边的话,则问题转化为 找尽量少的边把这些点都盖住,根据定理便是求最大匹配数.

#include <iostream>
    #include <fstream>
    
    using namespace std;
    #define MAXN 501
    
    int N,K;
    bool map[MAXN][MAXN],v[MAXN];
    int link[MAXN]; 
    
    bool dfs(int x)
    {
          
           int i;
           for(i=1; i<=N; i++)
           {
               if(!v[i] && map[x][i])
               {
                   v[i]=true;
                   if(link[i]==0 || dfs(link[i]))
                   {   
                       link[i]=x;
                       return true;
                   }
               }
           }
           return false;
    }
    
    int main()
    {
        int i,result=0;
        memset(map,false,sizeof(map));
        memset(link,0,sizeof(link));
        freopen("acm.txt","r",stdin);
        scanf("%d%d",&N,&K);
        for(i=1; i<=K; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            map[a][b]=true;
        }
        for(i=1; i<=N; i++)
        {
            memset(v,false,sizeof(v));
            if(dfs(i))
                result++;
        }
        printf("%d\n",result);
        return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/05/01/2477503.html

[http_www.cppblog.com_abilitytao_archive_2009_10_21_99124.aspx]: http://www.cppblog.com/abilitytao/archive/2009/10/21/99124.aspx