poj 3041 匈牙利算法最小点覆盖

ゝ一纸荒年。 2021-11-02 14:24 282阅读 0赞

题意：

一个N \* N的矩阵，每个格子有些行星，有种特殊武器，一次能消灭一行，或一列，问最少使用多少次这样得武器，可以消灭所有行星。

构图：

刚开始的思路是最少的边覆盖所有点，这个边是要么平行X轴，要么平行Y轴。

显然这样，这个边无法构图，起点终点都不知。

转换思路， 既然平行X轴，Y轴的边无法构造，是否可以平行X轴或Y轴的边把它看作一个点呢？

同时分成两个集合，一个集合X（1-N），一个集合Y（1-N），一个点（a,b)就从X集合中的点A

连一条边指向集合Y中的B。这样的定义构图就完全符合二分图的定义。

二分图的定义：

1.可以分成两个集合，一个X，一个Y

2.任何一条边的两个端点都分属于不同集合

3.任何一个集合内部不存在边

构图完毕，现在要解决得问题是如何用最少得点覆盖所有的边。

由匈牙利算法求这个二分图最大匹配就是答案，

也就是 最少覆盖点 = 最大匹配。证明 [http://www.matrix67.com/blog/archives/116][http_www.matrix67.com_blog_archives_116]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    int N, M;
    int mp[510][510];
    int match[510];
    bool color[510];
    
    int find( int x )
    {
      for( int i = 1; i <= N; i++)
      {
         if( !color[i] && mp[x][i] )
         {
             color[i] = true;
             if( match[i] == -1 || find( match[i] ))
             {
                match[i] = x;
                return 1;
             }
       
         }
    
      }
      return 0;
    }
    
    void solve( )
    {
       int ans = 0;
       memset(match,-1,sizeof(match));
       for( int i = 1; i <= N; i++)
       {
          memset(color, 0, sizeof(color));
          if( find(i) )
        ans++;
       }
       printf("%d\n",ans);
    }
    
    int main( )
    {
       int a, b;
       while( scanf("%d%d", &N, &M) != EOF)
       {
         for( int i = 1; i <= N; i++)
        for( int j = 1; j <= N; j++)
          mp[i][j] = 0;
         for( int i = 1; i <= M; i++)
         {
             scanf("%d%d",&a,&b);
             mp[a][b] = 1;
         }
         solve( );
       }
       return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/07/14/2591091.html

[http_www.matrix67.com_blog_archives_116]: http://www.matrix67.com/blog/archives/116
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/6bf7a4bad5134015a32dcef250ab3792.png