题解 | #[HNOI2006]超级英雄HERO#

思路

洛谷上额外要输出匹配方案，大家可以做一做，代码上注释了。
对每个问题进行二分图最大匹配，套一个匈牙利算法的模板，如果没有找到匹配，马上跳出。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;

struct E{
    int next,to;
}e[maxn<<2];

int n,m,u,v,ans;
int head[maxn],cnt;
int match[maxn],mt[maxn],vis[maxn],idx;

inline void addedge(int from,int to){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}

bool check(int x){
    for(int i=head[x];i;i=e[i].next){
        int to=e[i].to;
        if(vis[to]!=idx){
            vis[to]=idx;
            if(!match[to]||check(match[to])){
                match[to]=x;
                //mt[x]=to; 记录匹配方案
                return true;
            }
        }
    }
    return false;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        addedge(i,u+1);
        addedge(i,v+1);
    }
    for(int i=1;i<=m;i++){
        idx++; //时间戳 
        if(check(i)) ans++;
        else break;
    }
    cout<<ans<<endl;
    /*
    for(int i=1;i<=ans;i++){
        cout<<mt[i]-1<<endl;
    }
    */
    return 0;
}