题解 P3386 【【模板】二分图匹配】

# 二分图的最大匹配：匈牙利算法 讲之前本蒟蒻先普及一个重要**专业名词** ## 增广路。 如果你仔细读过并画过图，不难发现如果找到一条增广路，那么配对的个数就会加1。 所以说，增广路的本质其实就是一条路径的起点和终点都未配对的点的边。 ------------ ## 匈牙利算法： 这个叫匈牙利算法(Hungarian method)的东西是由匈牙利数学家Edmonds于1965年提出，所以叫**匈牙利算法**。匈牙利算法是二分图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 ### 复杂度： 时间复杂度 : 邻接矩阵最坏为O(n3) 邻接表： O(mn) 空间复杂度 : 邻接矩阵：O(n2) 邻接表： O(n+m) ## 另一个重要概念：二分图 二分图是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二分图。 ~~学过高中数学的话应该能看懂我在说什么（逃~~ 简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。满足这样的图就叫二分图。 #### 但我们怎么判断一个图是不是二分图？？？ 其实也不难，用红蓝点的方法就行。首先讲任意的一个顶点染成红色，再把这个点相邻的顶点染成蓝色，如果按照这种染色方式可以将所有的顶点全部着色，并且相邻的顶点的颜色不同，那么该图就是一个二分图。 ##### 这里贴一下代码 ```cpp #define MAXV 1000//这里应该根据题目自定 vector<int> G[MAXV]; //图 int V; //顶点数 int color[MAXV]; //顶点的颜色 （1 or -1） //顶点v，颜色c bool dfs(int v,int c){ color[v] = c; //把当前顶点相邻的顶点扫一遍 for(int i = 0;i < G[v].size(); i++){ //如果相邻顶点已经被染成同色了,说明不是二分图 if(color[G[v][i]] == c) return false; //如果相邻顶点没有被染色,染成-c,看相邻顶点是否满足要求 if(color[G[v][i]] == 0 && !dfs(G[v][i],-c)) return false; } //如果都没问题，说明当前顶点能访问到的顶点可以形成二分图 return true; } void solve(){ //可能是不连通图，所以每个顶点都要dfs一次 for(int i = 0;i < V; i++){ if(color[i] == 0){ //第一个点颜色为 1 if(!dfs(i,1)){ cout << "No" << endl; return; } } } } ``` # 这才是正文！！！ 既然上面本蒟蒻已经介绍完了有关二分图的知识，**那下面该讲下匈牙利算法了**！！！ 根据上文的描述，既然增广路的作用是“改进匹配方案”（即增加配对数），那么如果我们已经找到了一种匹配方案，不难发现如果在当前匹配方案下再也找不到任何增广路的话，那么当前匹配就是二分图的最大匹配，算法如下。 1.首先从任意的一个未配对的点u开始，从点u的边中任意选一条边（假设这条边是从u->v）开始配对。如果点v未配对，则配对成功，这是便找到了一条增广路。如果点v已经被配对，就去尝试“连锁反应”，如果这时尝试成功，就更新原来的配对关系。 所以这里要用一个matched[v] = u。配对成功就将配对数加1,。 2.如果刚才所选的边配对失败，那就要从点u的边中重新选一条边重新去试。直到点u 配对成功，或尝试过点u的所有边为止。 3.接下来就继续对剩下的未配对过的点一一进行配对，直到所有的点都已经尝试完毕，找不到新的增广路为止。 4.输出配对数。 ## CODE： ```cpp //如果你已经读完题，请自动从int main()处开始阅读 #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #define N 2010 using namespace std; int n,m,e,ans; int vis[N][N]; int ask[N],matched[N]; inline bool found(int x){ //dfs找增广路 for (int i = 1 ; i <= m ; i++) if (vis[x][i]){ if (ask[i]) continue; ask[i] = 1; if (!matched[i] || found(matched[i])) { matched[i] = x ; return true; } } return false; } inline void match(){ int cnt = 0;//cnt是计数器 memset(matched,0,sizeof(matched)); for (int i = 1 ; i <= n ; i++){ memset(ask,0,sizeof(ask)); if (found(i)) cnt++; //找到了就加1 } ans = cnt; } //从这里向下看起 int main(){ scanf("%d%d%d",&n,&m,&e);//结点个数分别为n,m，边数为e for (int i = 1 ; i <= e ; i++){ int x,y; scanf("%d%d",&x,&y); vis[x][y] = 1; } match();///匈牙利算法，见上 printf("%d \n",ans); return 0; } ``` ~~完结撒花（逃！！！~~