HDU 1054 Strategic Game (最小点覆盖)【二分图匹配】

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

解题分析：

最小点覆盖模板题，用最少的点来覆盖所有的边。建立无向图，然后求出其最大匹配，最小点覆盖数=最大匹配数。需要注意的是，本题用邻接矩阵存图跑匈牙利会T,所以用链式前向星存图。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N = 1500+10;
 7 int match[N],vis[N],head[N];
 8 int n,vN,vM,cnt;
 9 struct Edge{
10     int to,next;
11 }edge[N*N];   
12 void addedge(int u,int v){
13     edge[++cnt].to=v,edge[cnt].next=head[u];
14     head[u]=cnt;
15 }
16 bool dfs(int u){
17     for(int i=head[u];~i;i=edge[i].next){    //这层循环就是遍历能够与u匹配的节点
18         int v=edge[i].to;
19         if(!vis[v]){
20             vis[v]=1;
21             if(match[v]==-1||dfs(match[v])){
22                 match[v]=u;
23                 return true;
24             }
25         }
26     }
27     return false;
28 }
29 int Hungary(){
30     int ans=0;
31     memset(match,-1,sizeof(match));
32     for(int i=0;i<vN;i++){
33         memset(vis,0,sizeof(vis));
34         if(dfs(i))ans++;
35     }
36     return ans;
37 }
38 int main(){
39     while(scanf("%d",&n)!=EOF){
40         cnt=0;memset(head,-1,sizeof(head));
41         for(int i=1;i<=n;i++){
42             int u,v,k;scanf("%d:(%d)",&u,&k);
43             while(k--){
44                 scanf("%d",&v);
45                 addedge(u,v),addedge(v,u);   //存双向边
46             }
47         }
48         vN=vM=n;
49         int ans=Hungary();
50         printf("%d
",ans/2);   //最小点覆盖数=最大匹配数
51     }
52 }

2018-11-15