HDU 1054 Strategic Game 最小点覆盖

时间:2023-02-03 07:41:53

     最小点覆盖概念:选取最小的点数覆盖二分图中的所有边。

   最小点覆盖 = 最大匹配数。

   证明:首先假设我们求的最大匹配数为m,那么最小点覆盖必然 >= m,因为仅仅是这m条边就至少需要m个点。然后假如我们已经求得最小覆盖点集,那么在点集中每个点必然有着这样的性质,在于它相连的边里面,一定有一条边的端点不在最小点集中,因为如果连一条这样的边都没有,那这个点完全没有在最小点集的必要,我们任意选取这样的一条边,一定可以形成一个匹配,匹配数与最小点集中的点的个数相等,但现在这仅仅是一个匹配,他必然小于最大匹配,所以最小点覆盖 <= m,综上所述,最小点覆盖 = 最大匹配数,证明成立。

   ps:这个证明是我从网上看明白后总结出来的,个人感觉学姐的证明过于笼统,所以就放在了这里,感觉这个更加严密易懂(学知识要学明白嘛~)。

   代码如下:实现方法:基础匈牙利算法。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1510
int n;
struct EDGE
{
    int to,nxt;
} edge[10*maxn];
int head[maxn],vis[maxn],match[maxn],tot;
void add_edge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot++;
}
bool Find(int u)
{
    for(int i = head[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].to;
        if(!vis[v])
        {
            vis[v] = 1;
            if(match[v] == -1 || Find(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int slove()
{
    memset(match,-1,sizeof(match));
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        memset(vis,0,sizeof(vis));
        if(Find(i))
            ans++;
    }
    return ans;
}
int main()
{
    int num,a,b,t;
    while(~scanf("%d",&t))
    {
        n = t;
        memset(head,-1,sizeof(head));
        tot = 0;
        while(t--)
        {
            scanf("%d:(%d)",&a,&num);
            for(int i = 0;i < num;i++)
            {
                scanf("%d",&b);
                add_edge(a,b);
                add_edge(b,a);
            }
        }
        int ans = slove()/2;
        printf("%d\n",ans);
    }
    return 0;
}