HDU

题意：就是给出一棵树，然后你要尽可能少的在树上放置士兵，士兵会监视与其相连的结点。问怎样最少放置能够覆盖所有的结点
思路：这道题就是一道最小点覆盖问题，我们就把树看作一种图，然后建立无向图求解。 已知结论最小点覆盖 = 最大匹配数(无向图除以2)

完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int maxn = 1500;
const int maxm = 1e6+5;
struct Edge
{
    int v,next;
}edge[maxm];
int n;
int top ;
int head[maxn];
int vis[maxn];
int match[maxn];
void add(int u,int v){
    edge[top].v = v;
    edge[top].next = head[u];
    head[u] = top++;
}
bool dfs(int u){
    for(int i = head[u]; ~i;i = edge[i].next){
        int v = edge[i].v;
        if(!vis[v]){
            vis[v] = 1;
            if(!match[v]||dfs(match[v])){
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary(){
    int res = 0;
    memset(match,0,sizeof(match));
    for(int i =0;i<n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)) res++;
    }
    return res;
}
void init(){
    top = 0;
    memset(head,-1,sizeof(head));
    memset(edge,0,sizeof(edge));
}
int main(){
    while(~scanf("%d",&n)){
        init();
        for(int i = 0;i<n;i++){
            int a,b;
            scanf("%d:(%d)",&a,&b);
            for(int j =0;j<b;j++){
                int v;
                scanf("%d",&v);
                add(a,v);
                add(v,a);
            }
        }
        int ans = hungary();
        printf("%d
",ans/2);
    }
    return 0;
}