【模板】匈牙利算法

 1 #include<cstring>
 2 #include<vector>
 3 #define MAX_V 80
 4 
 5 int V;                               //顶点数
 6 int match[MAX_V];          //所匹配的顶点
 7 bool used[MAX_V];         //DFS中用到 的访问标记
 8 vector<int> G[MAX_V];   //图的邻接表表示
 9 
10 //向图中增加一条边接u和v的边
11 void add_edge(int u,int v)
12 {
13     G[u].push_back(v);
14     G[v].push_back(u);
15 }
16 
17 //通过DFS寻找增广路
18 bool dfs(int v)
19 {
20     used[v]=true;
21 
22     for(int i=0;i<G[v].size();i++)
23     {
24         int u=G[v][i],w=match[u];
25         if(w<0||(!used[w]&&dfs(w)))
26         {
27             match[v]=u;
28             match[u]=v;
29             return true;
30         }
31     }
32 
33     return false;
34 }
35 
36 //求解二分图的最大匹配
37 int bipartite_matching()
38 {
39     int res=0;
40 
41     memset(match,-1,sizeof(match));
42 
43     for(int v=1;v<=V;v++)
44     {
45         if(match[v]<0)
46         {
47             memset(used,false,sizeof(used));
48             if(dfs(v))
49                 res++;
50         }
51     }
52 
53     return res;
54 }