HDU1054Strategic Game(最小顶点覆盖数)

小鱼儿 2021-12-14 00:33 211阅读 0赞

我们来先了解一下什么是最小顶点覆盖；

图*G*的**顶点覆盖**是一个顶点集合*V*，使得*G*中的每一条边都接触*V*中的至少一个顶点。我们称集合*V*覆盖了*G*的边。***最小顶点覆盖***是用最少的顶点来覆盖所有的边。**顶点覆盖数**![\\tau][tau]是最小顶点覆盖的大小。

相应地，图*G*的**边覆盖**是一个边集合*E*，使得*G*中的每一个顶点都接触*E*中的至少一条边。

如果只说*覆盖*，则通常是指顶点覆盖，而不是边覆盖。

在二分图中  ：最大匹配数=最小顶点覆盖数；

求二分图最大匹配可以用最大流(Maximal Flow)或者[匈牙利算法][Link 1](Hungarian Algorithm)

所以下面介绍主要一下匈牙利算法：

[匈牙利算法][Link 1]是由匈牙利[数学家][Link 2]Edmonds于1965年提出，因而得名。匈牙利算法是基于[Hall定理][Hall]中充分性证明的思想，它是部图[匹配][Link 3]最常见的算法，该算法的核心就是寻找[增广路][Link 4]径，它是一种用增广路径求二分图最大匹配的算法。

在介绍 [匈牙利算法][Link 1]之前还是先提一下几个概念，下面M是G的一个匹配。

M-交错路：p是G的一条通路，如果p中的边为属于M中的边与不属于M但属于G中的边交替出现，则称p是一条M-交错路。如：路径（X3,Y2,X1,Y4），（Y1,X2,Y3）。

M-饱和点：对于v∈V(G），如果v与M中的某条边关联，则称v是M-饱和点，否则称v是非M-饱和点。如X1，X2，Y1，Y2都属于M-饱和点，而其它点都属于非M-饱和点。

M-可 [增广路][Link 4]：p是一条M-交错路，如果p的起点和终点都是非M-饱和点，则称p为M-可增广路。如（X3,Y2,X1,Y4）。（不要和流网络中的 [增广路][Link 4]径弄混了）

求最大 [匹配][Link 3]的一种 [显而易见][Link 5]的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的 [时间复杂度][Link 6]为边数的指数级 [函数][Link 7]。因此，需要寻求一种更加高效的算法。下面介绍用 [增广路][Link 4]求最大 [匹配][Link 3]的方法（称作 [匈牙利算法][Link 1]， [匈牙利][Link 8] [数学家][Link 2]Edmonds于1965年提出）。

[增广路][Link 4]的定义（也称增广轨或交错轨）：

若P是图G中一条连通两个未 [匹配][Link 3]顶点的路径，并且属于M的边和不属于M的边（即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条 [增广路][Link 4]径。

由 [增广路][Link 4]的定义可以推出下述三个结论：

1－P的路径个数必定为奇数，第一条边和最后一条边都不属于M。

2－将M和P进行取反操作可以得到一个更大的 [匹配][Link 3]M’。

3－M为G的最大 [匹配][Link 3]当且仅当不存在M的 [增广路][Link 4]径。

算法轮廓：

⑴置M为空

⑵找出一条 [增广路][Link 4]径P，通过异或操作获得更大的 [匹配][Link 3]M’代替M

⑶重复⑵操作直到找不出 [增广路][Link 4]径为止

接下来说说这题，经典的最小顶点覆盖题；

题意： 鲍勃喜欢玩电脑游戏，特别是战略游戏，但有时他无法找到解决方案，速度不够快，那么他很伤心。 现在，他有以下的问题。 他必须捍卫一个中世纪的城市，形成了树的道路。 他把战士的最低数量的节点上，使他们可以观察所有的边。 你能帮助他吗？ 士兵，鲍勃把一个给定的树，你的程序应该发现的最小数目。 输入文件包含多个数据集的文本格式。

题解：可以用匈牙利算法求解;用stl模版中的向量容器存放双向邻接表；

注意：1.本题中编号是从0开始；所以ret\[\]应初始化为-1；

2：向量要清零；

代码实现:

#include<stdio.h>
    #include<cstring>
    #include<vector>
    using namespace std;
    #pragma comment(linker,"/STACK:102400000,102400000")
    #define MAX   1505
    int visit[MAX];//标记节点是否被访问过；
    int ret[MAX];//标记n个节点的增广节点的编号
    vector<int>map[MAX];//用stl模版中的向量存放邻接表
    int find(int cur )//找增广路径
    {
         for(int i=0;i<map[cur].size();i++)
         {
              int j=map[cur][i];
              if(!visit[j])//若j与cur相邻，且没有被标记
              {
                   visit[j]=1;
                   if(ret[j]==-1||find(ret[j]))//如果j未在前一个匹配M中，或者，j在匹配M中，但从j相邻的节点出发可以找到增广路
                   {
                        ret[j]=cur;//则把cur放到匹配M中；
                        return 1;
                   }
              }
         }
         return 0;
    }
    int main()
    {
      // freopen("input.txt","r",stdin);
         int n,x,m,y;
         while(scanf("%d",&n)!=EOF)
         {
              for(int i=0;i<n;i++)map[i].clear();//注意要清零；
              for(int i=0;i<n;i++)
              {
                   scanf("%d:(%d)",&x,&m);
                   for(int j=0;j<m;j++)
                   {
                        scanf("%d",&y);
                        map[x].push_back(y);//用向量存放双向邻接表
                        map[y].push_back(x);
                   }
              }
              int sum=0;
              memset(ret,-1,sizeof(ret));//因为节点从0开始，所以要赋值为-1；
              for(int i=0;i<n;i++)//
              {
                   memset(visit,0,sizeof(visit));
                   sum+=find(i);//若有增广路，匹配数则加一
              }
              printf("%d\n",sum/2);//最小顶点覆盖 == 最大匹配（双向图）/2；
         }
       return 0;
    }

转载于:https://www.cnblogs.com/james1207/p/3266549.html

[tau]: /images/20211213/dfabc4d6af854187a17abdfd63701c00.png
[Link 1]: http://baike.baidu.com/view/501092.htm
[Link 2]: http://baike.baidu.com/view/66878.htm
[Hall]: http://baike.baidu.com/view/4509786.htm
[Link 3]: http://baike.baidu.com/view/352573.htm
[Link 4]: http://baike.baidu.com/view/3585026.htm
[Link 5]: http://baike.baidu.com/view/82912.htm
[Link 6]: http://baike.baidu.com/view/104946.htm
[Link 7]: http://baike.baidu.com/view/15061.htm
[Link 8]: http://baike.baidu.com/view/6397.htm