HDU 1054 hungary

题

HDU

解

题意：最小顶点覆盖。

hungary求最大匹配出来就行了。
好像网上都说要除以2……但是我没除还是A啊……
想了想也许他们的代码是求出匹配的顶点数……？（想不通）（。
至于这个结论怎么证，想了想离散数学的套路，应该就是

在最大匹配之中全部取某一个端点，若是还有一些边没选到，则按照增广路定理并将有更优的匹配，从而与最大匹配的前提矛盾。

讲真我细节真不会……也就嘴巴说说想法而已……

码（1876K, 951ms）

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e4;
int V;
vector<int> G[maxn];
int match[maxn];
bool used[maxn];

void add_edge(int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

bool dfs(int v)
{
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++)
    {
        int u = G[v][i], w = match[u];
        if(w < 0 || !used[w] && dfs(w))
        {
            match[u] = v;
            match[v] = u;
            return true;
        }
    }
    return false;
}

int matching()
{
    int ans = 0;
    memset(match, -1, sizeof match);
    for(int v = 0; v < V; v++)
    {
        if(match[v] < 0)
        {
            memset(used, false, sizeof used);
            if(dfs(v))
                ans++;
        }
    }
    return ans;
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        V = n;
        for(int i = 0; i <= n; i++)
            G[i].clear();
        while(n--)
        {
            int ni, nr;
            scanf("%d:(%d)", &ni, &nr);
            while(nr--)
            {
                int a; read(a);
                add_edge(ni, a);
            }
        }
        printf("%d\n", matching());
    }
    return 0;
}