OI

【模板】匈牙利算法

解决二分图最大匹配的快速算法，打起来比网络流快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<memory.h>
const int MAXN=1005;
const int MAXM=2005;
bool g[MAXN][MAXM]={0},y[MAXM];
int link[MAXM]={0};
int n,m,e,ans;

bool find(int v){
    int i;
    for(i=1;i<=m;i++)
        if(g[v][i]&&!y[i]){
            y[i]=1;
            if(link[i]==0||find(link[i])){
                link[i]=v;
                return true;
            }
        }
    return false;
}

int main(){
    int i,j,a,b,t;
    memset(g,0,sizeof(g));
    memset(link,0,sizeof(link));
    ans=0;
    for(i=1;i<=n;i++){
      memset(y,0,sizeof(y));
      if(find(i))ans++;
    }

    return 0;
}