bzoj1191 题解

二分图匹配。

有一点需要注意，题目里说：

只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰

也就是说，对于问题i增广失败的话，说明问题i无论如何也答不上来，那么后面的问题就不用管了，因为都不能答。

二分图匹配的时候，会把点分成两部分，对于一边的点dfs，在这道题里，只能对题目来dfs。

代码：

#include <cstdio>
#include <cstring>
#define ele int
using namespace std;
#define maxn 2010
#define maxm 2010
struct edge{
    ele v;
    edge *nxt;
}pool[maxm<<1];
ele n,m,cnt,to[maxn<<1];
bool flag[maxn<<1];
edge *h[maxn];
inline void addedge(ele u,ele v){
    edge *p=&pool[cnt++];
    p->v=v; p->nxt=h[u];
    h[u]=p;
}
inline void init(){
    ele x,y;
    scanf("%d%d",&n,&m);
    cnt=0;
    memset(h,0,sizeof(h));
    for (int i=0; i<m; ++i){
        scanf("%d%d",&x,&y);
        addedge(i,m+x); addedge(m+x,i);
        if (x!=y)
            addedge(i,m+y),addedge(m+y,i);
    }
    for (int i=0; i<n; ++i) to[m+i]=-1;
}
bool dfs(ele i){
    for (edge *j=h[i]; j; j=j->nxt)
        if (!flag[j->v]){
            flag[j->v]=true;
            if (to[j->v]==-1 || dfs(to[j->v])){
                to[j->v]=i;
                return true;
            }
        }
    return false;
}
inline void solve(){
    ele ans=0;
    for (int i=0; i<m; ++i){
        memset(flag,0,sizeof(flag));
        if (dfs(i)) ++ans; else break;
    }
    printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}