欢迎访问~原文出处——

---

---

题目概括

　　有m个题目，有n个解决方案；对于每一个题目，有两种解决方案可用。

　　每种解决方案只能用一次，问最多可以通过最前面的几题？

---

 

题解

　　几乎是裸的二分图匹配。

　　每个题目两条边，分别连向所对应的两种解决方案。

　　然后跑匈牙利算法。具体可以看，往后翻就有匈牙利算法的解说。

　　可怕的是，我之前以为是最多可以通过几道。

　　白白wa了很久……

　　其实是从第一题开始，最多可以连续通过几道。

---

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=2000+5,M=N;struct Gragh{    int cnt,x[M],y[M],nxt[M],fst[N];    void set(){        cnt=0;        memset(fst,0,sizeof fst);    }    void add(int a,int b){        x[++cnt]=a,y[cnt]=b;        nxt[cnt]=fst[a],fst[a]=cnt;    }}g;int n,m,cnt,vis[N],match[N];bool dfs(int x){    for (int i=g.fst[x];i;i=g.nxt[i])        if (!vis[g.y[i]]){            vis[g.y[i]]=1;            if (match[g.y[i]]==-1||dfs(match[g.y[i]])){                match[g.y[i]]=x;                return 1;            }        }    return 0;}int main(){    scanf("%d%d",&n,&m);    g.set();    memset(match,-1,sizeof match);    cnt=0;    for (int i=1,a,b;i<=m;i++){        scanf("%d%d",&a,&b);        a++,b++;        g.add(i,m+a);        g.add(i,m+b);        memset(vis,0,sizeof vis);        if (dfs(i))            cnt++;        else            break;    }    printf("%d",cnt);    return 0;}