题意
求二分图最大匹配。
思路
教学题，只要使用了二分图／网络流就可以通过。在这里我强行使用了Hopcroft-Karp Algorithm，因为看了很长时间自己也很难理解，决定抄一遍别人的代码仔细领悟。核心部分我加了好多注释帮助理解。
代码
|
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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; #pragma mark - Hopcroft-Karp Algorithm for BiGraph Matching (BGM_HK) const int MAXN = 210; const int INF = 0x3f3f3f3f; 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 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(){ memset(first, -1, sizeof(first)); memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); } bool 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 = 0; 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 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 || 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 (bfs()) { memset(ap_vis, false, sizeof(ap_vis)); for (int i = 0; i < nx; i++) { if (matchX[i] == -1) { ans += dfs(i); } } } return ans; } #pragma mark - int main(){ int n,m; while (scanf(" %d %d",&n,&m) != EOF) { nx = n,ny = m; init(); for (int i = 0; i < n; i++) { X[i].to.clear(); } for (int i = 0; i < m; i++) { Y[i].to.clear(); } for (int i = 0; i < n; i++) { int q; scanf(" %d",&q); for (int j = 1; j <= q; j++) { int tmp; scanf(" %d",&tmp); tmp--; X[i].to.push_back(tmp); Y[tmp].to.push_back(i); } } cout << BGM_HK() << endl; } } |
August 29, 2015
[…] POJ 1274 The Perfect Stall（教学题） POJ 2446 Chessboard（骨牌模型转化） POJ 2594 Treasure Exploration（允许相交的最小路径覆盖） POJ 1325 Machine Schedule（适当建图，最小点覆盖问题） POJ 1469 COURSES（教学题） HDU 3225 Flowers Placement（匈牙利算法在DFS中的剪枝作用） […]