知识
二分图大讲堂——彻底搞定最大匹配数(最小覆盖数)、最大独立数、最小路径覆盖、带权最优匹配
这一篇已经足够了。
模板
匈牙利算法,复杂度O(V*E),使用“vector邻接表”存储图。MAXN为单边最大节点数量,需要按照题目要求调整,INF是理论最大值不够的话按照题目要求调整。左手边和右手边的节点序号从0开始,建图前,执行init,并正确配置nx(左手边节点数量)和ny(右手边节点数量),BGM_H()返回最大匹配数。
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H) const int MAXN = 1050; struct Node{ vector<int> to; } X[MAXN],Y[MAXN];//index starts from 0 int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y] bool ap_vis[MAXN];//vis marking array for augment path searching void init(){ for (int i = 0; i < MAXN; i++) { X[i].to.clear(); Y[i].to.clear(); } memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); } int ap_dfs(int u){ for (int i = 0; i < X[u].to.size(); i++) { int v = X[u].to[i]; if (!ap_vis[v]) { ap_vis[v] = true; if (matchY[v] == -1 || ap_dfs(matchY[v])) { matchX[u] = v; matchY[v] = u; return 1; } } } return 0; } int BGM_H(){ int ret = 0; memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); for (int i = 1; i < nx; i++) { if (matchX[i] == -1) { memset(ap_vis, false, sizeof(ap_vis)); if (ap_dfs(i)) { ret++; } } } return ret; } #pragma mark - |
Hopcroft-Karp算法,复杂度O(sqrt(V) * E),适配方法同匈牙利算法模板,调用是BGM_HK(),不适合活用。
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#pragma mark - Hopcroft-Karp Algorithm for BiGraph Matching (BGM_HK) const int MAXN = 350; const int INF = 0x3f3f3f3f; struct Node{ vector<int> to; } X[MAXN],Y[MAXN];//index starts from 1 int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny int dis; int first[MAXN]; int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y] int disX[MAXN],disY[MAXN]; bool ap_vis[MAXN];//vis marking array for augment path searching void init(){ for (int i = 0; i < MAXN; i++) { X[i].to.clear(); Y[i].to.clear(); } memset(first, -1, sizeof(first)); memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); } bool hk_bfs(){ queue<int> que; dis = INF;//records currently the smallest distance(length of the augmented path) memset(disX, -1, sizeof(disX));//reset disX and disY array to the status indicating that no match was made memset(disY, -1, sizeof(disY)); for (int i = 1; i <= nx; i++) { //iterate the LHS and find any available not-matched nodes if (matchX[i] == -1) { //if this node is not matched,add this node into the queue que.push(i); //the distance(length of the augmented path) should be zero for a bold, unmatched point disX[i] = 0; } } while (!que.empty()) { int u = que.front();//"current node" que.pop(); if (disX[u] > dis) { //if the augmented path derived from u is larger than someone we had examined,we don't need to examine this point anymore break; } for (int i = 0; i < X[u].to.size(); i++) { //iterate the nodes connected with current node (all connected nodes are,certainally, belongs to RHS) int v = X[u].to[i]; if (disY[v] == -1) { //if the distance data is void for the connected RHS node,we should update it disY[v] = disX[u] + 1; if (matchY[v] == -1) { //in this case, we can terminate the current augment path here dis = disY[v]; }else { //in this case,we try to go deeper on the existed augment path disX[matchY[v]] = disY[v] + 1; que.push(matchY[v]); } } } } return dis != INF;//if dis == INF, this means no longer augment path can be made } int ap_dfs(int u){ //the current LHS node is u for (int i = 0; i < X[u].to.size(); i++) { //iterate the connected RHS node v int v = X[u].to[i]; if (!ap_vis[v] && disY[v] == disX[u] + 1) { //we want to find a non-visited RHS node with the desired distance ap_vis[v] = true;//mark visited if (matchY[v] != -1 && disY[v] == dis) { //if this node has already matched and the distance is what we desired --> appropriate augment path exist, no need to advance continue; } if (matchY[v] == -1 || ap_dfs(matchY[v])) { //hangary algo. //if matchY = -1 --> augment path terminated,else go deeper matchX[u] = v; matchY[v] = u; return 1; } } } return 0; } int BGM_HK(){ int ans = 0; while (hk_bfs()) { memset(ap_vis, false, sizeof(ap_vis)); for (int i = 1; i <= nx; i++) { if (matchX[i] == -1) { ans += ap_dfs(i); } } } return ans; } #pragma mark - |
配套练习
二分图・ア:
POJ 1274 The Perfect Stall(教学题)
POJ 2446 Chessboard(骨牌模型转化)
POJ 2594 Treasure Exploration(允许相交的最小路径覆盖)
POJ 1325 Machine Schedule(适当建图,最小点覆盖问题)
POJ 1469 COURSES(教学题)
HDU 3225 Flowers Placement(匈牙利算法在DFS中的剪枝作用)