题目链接:
https://www.luogu.org/problemnew/show/P2319
分析
每错,这是一道海南不对是河南呀呀呀错了是湖南的省选题。
但是还是可以作为二分图第二题来练手的,插播第一题,对照食用效果更佳
言归正传。
这道题说
只有正确回答本题才能进入下一题
于是我们就可以循环题目编号以保证符合题意。
然后由于题目不但让我们输出最多能通过几题,还要求输出锦囊妙计的编号,于是我们可以在find模板函数中记录一下:
sum[x]=p;
即可。
然后我们还是要考虑一下else break;
的问题。
因为这时后还是要求连续的答题,所以说一道题如果没答上(!find(i)),那么就被淘汰了。所以也要加上。(后面有不加else break的题目情况)
代码:
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
vector<int>v[1005];
int vis[1005],link[1005],a[1005],sum[1005];
int t;
bool find(int x)
{for(int i=0;i<v[x].size();i++){int p=v[x][i];if(vis[p]!=t){vis[p]=t;if(link[p]==-1||find(link[p])){link[p]=x;sum[x]=p; return 1;}}}return 0;
}
int main()
{int n,m;for(int i=0;i<=1000;i++){link[i]=-1;}scanf("%d%d",&m,&n);int maxf=0;for(int i=0;i<n;i++){int a,b;scanf("%d%d",&a,&b);v[i].push_back(a);v[i].push_back(b);} int cnt=0;for(int i=0;i<=n+m;i++)//在这里n+m是为了防止最后一个被忽略的情况{t++;if(find(i)){cnt++;}elsebreak;}printf("%d\n",cnt);for(int i=0;i<cnt;i++){printf("%d\n",sum[i]);}return 0;
}