题解

本题使用**二分图匹配（匈牙利算法）**求解答题顺序问题。

算法思路：

1. 问题建模：

   • 将问题转化为二分图匹配问题
   • 左侧节点：$m$ 道题目（按出现顺序编号 $0 \sim m-1$）
   • 右侧节点：$n$ 种解法（编号 $1 \sim n$）
   • 边：第 $i$ 道题可以用解法 $a$ 或解法 $b$ 解决

2. 匈牙利算法：

   • 按题目顺序依次尝试匹配
   • 对于第 $i$ 道题，使用 DFS 寻找增广路径：
     • 尝试将该题匹配到解法 $a$ 或 $b$
     • 如果解法已被占用，尝试为之前占用该解法的题目重新分配其他解法
     • 如果能找到增广路径，匹配成功

3. 贪心策略：

   • 题目必须按顺序回答，不能跳过
   • 如果第 $i$ 道题无法找到可用的解法，则从第 $i$ 道题开始之后的所有题都无法回答
   • 使用 break 终止匹配过程

4. 匹配记录：

   • match[j]：记录解法 $j$ 被哪道题使用
   • bematch[i]：记录第 $i$ 道题使用了哪个解法
   • rec[j]：标记解法 $j$ 在当前轮DFS中是否已被访问

5. 答案输出：

   • 统计成功匹配的题目数量 cnt

时间复杂度：$O(m \cdot n \cdot m) = O(m^2 n)$，最坏情况下每道题需要遍历所有解法和之前的题目。

#include<bits/stdc++.h>
using namespace std;
const int MAX=1111;
int n,m,match[MAX],bematch[MAX];//用于记录第i题用的方法，并且输出答案
int h[MAX],e[MAX*2],ne[MAX*2],idx;//大小开两倍
bool rec[MAX];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx,idx++;
}
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!rec[j]){
            rec[j]=true;
            if(match[j]==-1||find(match[j])){
                match[j]=x;
                bematch[x]=j;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(i,a),add(i,b);
    }
    memset(match,-1,sizeof match);//从0开始，那就初始化-1 ，其实也可以在题目给的数值上加1，然后输出的时候减一就行
    int cnt=0;
    for(int i=0;i<m;i++){
        memset(rec,false,sizeof rec);
        if(find(i))cnt++;
        else break;//有一题找不到答案就不能继续答下去了，就break啦
    }
    cout<<cnt<<endl;

}