题目描述 现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。
这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？
输入格式 输入的第一行是两个正整数 n 和 m (0 < n < 1001, 0 < m < 1001)表示总共有 n 种“锦囊妙计”，编号为 0 ∼ n − 1 0 \sim n-1 0∼n−1 ，总共有 m 个问题。
以下的m行，每行两个数，分别表示第 m 个问题可以使用的“锦囊妙计”的编号。
注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。
输出格式 输出的第一行为最多能通过的题数 p，接下来 p 行，每行为一个整数，第 i 行表示第 i 题使用的“锦囊妙计的编号”。
如果有多种答案，那么任意输出一种，本题使用 Special Judge 评判答案。
输入输出样例 输入
5 6 3 2 2 0 0 3 0 4 3 2 3 2输出
4 3 2 0 4思路： 这一题和最大匹配的模板差不多，但是有一个小坑。
题目规定：主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。
所以当我们跑最大匹配没有匹配时，就要break。
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N=2e3+10; struct node { int u, v, next; } edge[N]; int n, m, a, b, hd[N], tot, ans, link[N], ans1[N]; bool cover[N]; void add(int u, int v) {edge[++tot]=(node){u, v, hd[u]},hd[u]=tot;} bool find(int x) { for(int i=hd[x]; i; i=edge[i].next) { int y=edge[i].v; if(!cover[y]) { cover[y]=1; int q=link[y], q1=ans1[x]; link[y]=x, ans1[x]=y; if(!q || find(q)) return 1; link[y]=q, ans1[x]=q1; } } return 0; } int main() { scanf("%d%d", &n, &m); for(int i=1; i<=m; i++) { scanf("%d%d", &a, &b); add(i, a); if(a != b) add(i, b); } for(int i=1; i<=m; i++) { memset(cover, 0, sizeof(cover)); if(find(i)) ans++; else break; //小坑：不能匹配时就要break } printf("%d\n", ans); for(int i=1; i<=ans; i++) printf("%d\n", ans1[i]); //为什么可以是1~ans,因为答题是按顺序的（1~ans） return 0; }