链接：

pid=1054">http://acm.hdu.edu.cn/showproblem.php?pid=1054

题意：一个熊孩子玩策略游戏，他须要用最少的士兵守卫最多的道路。假设这个顶点有士兵。则和这个点相连的全部边都会被保护，问保护全部的道路最少须要的士兵数量。

思路：这实际上就是一个最小点覆盖，二分图的最小点覆盖 == 最大匹配，这不是一个二分图，我们把n个点扩成2 * n个。把他转换为二分图，最后最大匹配再除以2就是原图的最大匹配。

Hopcroft-Karp增广模板

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 1510

#define eps 1e-7

#define INF 0x3F3F3F3F      //0x7FFFFFFF

#define LLINF 0x7FFFFFFFFFFFFFFF

#define seed 1313131

#define MOD 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

/*

二分图匹配（Hopcroft-Carp的算法）。

顶点下标从0開始

调用：res=MaxMatch();  Nx,Ny要初始化！！！

时间复杂大为 O(V^0.5 E)

适用于数据较大（点较多）的二分匹配

*/

struct node{

    int v,next;

}edge[MAXN*MAXN];

int head[MAXN],cnt;

int Mx[MAXN],My[MAXN],Nx,Ny;

int dx[MAXN],dy[MAXN],dis;

bool vis[MAXN];

void add_edge(int a,int b){

    edge[cnt].v = b;

    edge[cnt].next = head[a];

    head[a] = cnt++;

}

bool searchP(){

    queue<int>q;

    dis = INF;

    memset(dx,-1,sizeof(dx));

    memset(dy,-1,sizeof(dy));

    for(int i = 0; i < Nx; i++)

        if(Mx[i] == -1){

            q.push(i);

            dx[i] = 0;

        }

    while(!q.empty()){

        int u = q.front();

        q.pop();

        if(dx[u] > dis)  break;

        for(int i = head[u]; i != -1; i = edge[i].next){

            int v = edge[i].v;

            if(dy[v] == -1){

                dy[v] = dx[u] + 1;

                if(My[v] == -1) dis = dy[v];

                else{

                    dx[My[v]] = dy[v] + 1;

                    q.push(My[v]);

                }

            }

        }

    }

    return dis != INF;

}

bool DFS(int u){

    for(int i = head[u]; i != -1; i = edge[i].next){

        int v = edge[i].v;

        if(!vis[v] && dy[v] == dx[u] + 1){

            vis[v] = 1;

            if(My[v] != -1 && dy[v] == dis) continue;

            if(My[v] == -1 || DFS(My[v])){

                My[v] = u;

                Mx[u] = v;

                return 1;

            }

        }

    }

    return 0;

}

int MaxMatch(){

    int res = 0;

    memset(Mx,-1,sizeof(Mx));

    memset(My,-1,sizeof(My));

    while(searchP()){

        memset(vis,0,sizeof(vis));

        for(int i = 0; i < Nx; i++)

          if(Mx[i] == -1 && DFS(i))  res++;

    }

    return res;

}

int main(){

    int n,i,j;

    int a,m,b;

    while(scanf("%d", &n)!=EOF){

        cnt = 0;

        memset(head,-1,sizeof(head));

        for(i = 0; i < n; i++){

            scanf("%d:(%d)", &a, &m);

            while(m--){

                scanf("%d", &b);

                add_edge(a,b);

                add_edge(b,a);

            }

        }

        Nx = Ny = n;

        int ans = MaxMatch();

        printf("%d\n", ans / 2);

    }

    return 0;

}