Strategic Game HDU - 1054（最小顶点覆盖）

最小顶点覆盖：用最少的点，让每条边都至少和其中一个点关联；

。。。以为自己很聪明。。用边连边。。。最后还是点连点  哎。。。。

hc 写的  匈牙利足够/////

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#include <cmath>

#include <vector>

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

const int maxn = , INF = 0x7fffffff;

int dx[maxn], dy[maxn], cx[maxn], cy[maxn], used[maxn];

int nx, ny, dis, n;

vector<int> G[maxn];

int bfs()

{

    queue<int> Q;

    dis = INF;

    mem(dx, -);

    mem(dy, -);

    for(int i=; i<=nx; i++)

    {

        if(cx[i] == -)

        {

            Q.push(i);

            dx[i] = ;

        }

    }

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        if(dx[u] > dis) break;

        for(int v=; v<G[u].size(); v++)

        {

            int i = G[u][v];

            if(dy[i] == -)

            {

                dy[i] = dx[u] + ;

                if(cy[i] == -) dis = dy[i];

                else

                {

                    dx[cy[i]] = dy[i] + ;

                    Q.push(cy[i]);

                }

            }

        }

    }

    return dis != INF;

}

int dfs(int u)

{

    for(int v=; v<G[u].size(); v++)

    {

        int i = G[u][v];

        if(!used[i] && dy[i] == dx[u] + )

        {

            used[i] = ;

            if(cy[i] != - && dis == dy[i]) continue;

            if(cy[i] == - || dfs(cy[i]))

            {

                cy[i] = u;

                cx[u] = i;

                return ;

            }

        }

    }

    return ;

}

int hk()

{

    int res = ;

    mem(cx, -);

    mem(cy, -);

    while(bfs())

    {

        mem(used, );

        for(int i=; i<=nx; i++)

        {

            if(cx[i] == - && dfs(i))

                res++;

        }

    }

    return res;

}

int main()

{

    while(cin>> n)

    {

        for(int i=; i<maxn; i++) G[i].clear();

        for(int i=; i<n; i++)

        {

            int u, m;

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

            for(int j=; j<m; j++)

            {

                int v;

                scanf("%d",&v);

                G[u].push_back(v);

                G[v].push_back(u);

            }

        }

        nx = ny = n-;

    //    cout<< rt<< "  " << nx << "   " <<endl;

        cout<< hk()/ <<endl;

    }

    return ;

}