【bzoj1191】【HNOI2006】【超級英雄】【Hero】【二分圖比對】

題目大意

給出一些題目，每題有兩個錦囊，用其中一個一定能解決一道題，必須按順序解決題目，求最多可以解決多少道題目。

解題思路

顯然用匈牙利做二分圖比對，注意按順序做，一旦有一個失配就停止并輸出答案。

code

#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const maxn=,maxm=;
int n,m,to[maxm+][],pai[maxn+];
bool visit[maxn+];
bool match(int now){
    visit[now]=;
    fo(i,,){
        int next=to[now][i];
        if((!pai[next])||((!visit[pai[next]])&&(to[pai[next]][])&&(match(pai[next])))){
            pai[next]=now;
            return ;
        }
    }
    return ;
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d%d",&n,&m);
    int ans=;
    fo(i,,m){
        scanf("%d%d",&to[i][],&to[i][]);to[i][]=;
        if(match(i))ans++;
        else break;
        memset(visit,,sizeof(visit));
    }
    printf("%d",ans);
    return ;
}