P2319 [HNOI2006]超级英雄

P2319 [HNOI2006]超级英雄

最大匹配即可，不一样的是一旦有一个不能匹配，立刻退出。匈牙利即可。

查看代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e3 + 10;
bool vis[N];
int n, m, sum, ans[N], match[N];
pair <int, int> k[N];
bool dfs (int x)
{
    if (!vis[k[x].first])
    {
        vis[k[x].first] = true;
        if (match[k[x].first] == -1 || dfs(match[k[x].first]))
        {
            match[k[x].first] = x;
            return true;
        }
    }
    if (!vis[k[x].second])
    {
        vis[k[x].second] = true;
        if (match[k[x].second] == -1 || dfs(match[k[x].second]))
        {
            match[k[x].second] = x;
            return true;
        }
    }
}
int main ()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        match[i] = -1;
    for (int i = 0; i < m; i++)
        ans[i] = -1;
    for (int i = 0; i < m; i++)
        cin >> k[i].first >> k[i].second;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            vis[j] = false;
        if (!dfs(i))
            break;
        sum++;
    }
    cout << sum << endl;
    for (int i = 0; i < n; i++)
        if (~match[i])
            ans[match[i]] = i;
    for (int i = 0; i < m; i++)
        if (~ans[i])
            cout << ans[i] << endl;
    return 0;
}