https://www.luogu.org/problem/P2319
主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？
就把问题作为左边的点，单向指向右边的锦囊妙计
to[]为右边的锦囊妙计指向(回答)的问题
ans[]为这个问题用那个锦囊妙计
因此保证了每个find()的x都都是左边的问题，因此问题编号和锦囊妙计的编号并不会混乱
由此看来，二分图最大匹配还是很灵活的
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define ri register int #define u int #define NN 5005 #define MM 100005 namespace fast { inline u in() { u x(0); char s=getchar(); while(s<‘0‘||s>‘9‘) { s=getchar(); } while(s>=‘0‘&&s<=‘9‘) { x=(x<<1)+(x<<3)+s-‘0‘; s=getchar(); } return x; } } using fast::in; namespace all { u cnt,N,M,to[NN],ans[NN],vt[NN],h[NN]; struct node { u to,next; } a[MM<<1]; inline void add(const u &x,const u &y) { a[++cnt].next=h[x],a[cnt].to=y,h[x]=cnt; } u find(const u &x){ for(ri i(h[x]);i;i=a[i].next){ u _y(a[i].to); if(vt[_y]) continue; vt[_y]=1; if(!to[_y]||find(to[_y])){ to[_y]=x,ans[x]=_y; return 1; } } return 0; } inline void solve(){ N=in(),M=in(); for(ri i(1);i<=M;++i){ u _a(in()),_b(in()); add(i,_a+1),add(i,_b+1); } for(ri i(1);i<=M;++i){ if(!ans[i]){ memset(vt,0,sizeof(vt)); if(!find(i)) break; else ++ans[0]; } } printf("%d\n",ans[0]); for(ri i(1);i<=ans[0];++i){ printf("%d\n",ans[i]-1); } } } int main() { //freopen("x.txt","r",stdin); all::solve(); }
原文：https://www.cnblogs.com/ling-zhi/p/11621793.html