题目链接: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;
}