HDU1151-Air Raid(最小边覆盖)

题目链接:HDU1151-Air Raid

题意:

给n个点,m条单向边,求最小边覆盖。

题解:

最小边覆盖=总点数-最大匹配数。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 * 2;
const int MAXM = 200 * 2;
int T, n, m;
int match[MAXN];
bool used[MAXN];
struct EDGE
{
    int v, nxt;
} edge[MAXM * 2];
int cnt = 0, fir[MAXN];
void addedge(int u, int v)
{
    edge[cnt].v = v;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
bool dfs(int u)
{
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (!used[v])
        {
            used[v] = 1;
            if (match[v] == -1 || dfs(match[v]))
            {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int MaxMatch()
{
    int sum = 0;
    memset(match, -1, sizeof(match));
    for (int i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (dfs(i))
            sum++;
    }
    return sum;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        cnt = 0;
        memset(fir, -1, sizeof(fir));
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v + n);
        }
        int ans = MaxMatch();
        printf("%d\n", n - ans);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。