P 3386【テンプレート】二分図マッチング

転送ゲート:P 3386【テンプレート】二分図マッチング
二分図の最大マッチングで最もよく用いられるアルゴリズムはハンガリーアルゴリズムであり,すなわち拡張路から最大マッチングを求める.
詳しくは右側のリンクをクリックしてください:趣写アルゴリズムシリーズの--ハンガリーアルゴリズム

//        ——     ，          
//#define LOCAL
#include
#include
#include
using namespace std;
const int maxn=1010;
int n,m,e,vis[maxn],link[maxn],mp[maxn][maxn];

bool match(int x){
    for(int i=1;i<=m;i++){
        if(mp[x][i]&&!vis[i]){
            vis[i]=1;
            if(link[i]==-1||match(link[i])){
                link[i]=x;
                return true;
            }
        }
    }
    return false;
}

int hungry(){
    int tot=0;
    memset(link,-1,sizeof(link));
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(match(i)) tot++;
    }
    return tot;
}

int main(){
#ifdef  LOCAL
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
#endif
    scanf("%d%d%d",&n,&m,&e);
    int u,v;
    memset(mp,0,sizeof(mp));
    for(int i=0;i