题意
求第k小的二分图最大匹配方案。
思路
这个题需要我们活用匈牙利算法了。首先正常地建图，运行一次匈牙利算法，这样初步得到了一种最大匹配样态。
接下来，我们使用DFS，从第一束花开始，从小到大挨个枚举这一位放什么，对于每一次枚举，首先要检查在当前已经有的匹配里面是不是这种花已经被匹配过了，如果是的话要解除这一匹配，接下来我们要把这一位在二分图中的匹配指向被枚举的那种花，如果被枚举的那种花原来是指向当前位置的，我们可以直接继续搜索，因为二分图可以继续有机会保持匹配，否则的话我们要以被枚举的那种花原来的东家为起点，进行一次增广路搜索（即匈牙利算法中的一环），如果没有搜索到增广路，说明这样下去也不可能出现最大匹配，可以剪枝了。
注意，如果增广路搜索失败，要把启动搜索之前的那些临时性修改复原，如果增广路搜索成功，那些修改就可以保留了。在增广路搜索过程中，注意不可以让增广路搜索修改当前DFS深度之前的已经固定了的节点。
当深度到达n时，就可以知道当前是一种合法的最大匹配样态，我们可以给计数器＋1，当计数器到达k时，中断DFS过程，纪录回溯路径就是答案了。
这种方法可能有一些难以理解，其实只要把增广路过程给当成一种把当前的图给变成匹配了的图的一种“尝试修复”的过程就好了，如果尝试成功，说明以当前图的形态，还有机会出现最大匹配，如果尝试适失败，说明当前图的形态没有前途，不用再深入考虑了。
代码
|
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 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
#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 - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H) const int MAXN = 201; 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 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 prog; int ap_dfs(int u){ if (u <= prog) { return false; } 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; } #pragma mark - int cnt; int n,m,k; bool vis[201]; stack<int> ans; bool dfs(int u){ if (u == n+1) { cnt++; if (cnt == k) { return true; } } for (int i = 0; i < X[u].to.size(); i++) { int v = X[u].to[i]; if (!vis[v]) { prog = u; memset(ap_vis, 0, sizeof(ap_vis)); bool flag = (matchY[v] == u); int resumej = 0,resumejn = 0,resumeun; for (int j = 1; j <= n; j++) { if (matchY[j] == u) { resumej = j; resumejn = matchY[j]; matchY[j] = -1; } } resumeun = matchX[u]; matchX[u] = v; int orig = matchY[v]; matchY[v] = u; if (flag || ap_dfs(orig)) { vis[v] = true; if(dfs(u+1)){ ans.push(v); return true; } vis[v] = false; }else{ matchY[resumej] = resumejn; matchX[u] = resumeun; matchY[v] = orig; } } } return false; } 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)); ret += ap_dfs(i); } } return ret; } bool board[201][201]; int main(){ int caseCnt; scanf(" %d",&caseCnt); for (int d = 1; d <= caseCnt; d++) { init(); scanf(" %d %d %d",&n,&m,&k); memset(board, true, sizeof(board)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { int num; scanf(" %d",&num); board[j][num] = false; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (board[i][j]) { X[i].to.push_back(j); } } } nx = ny = n; cnt = 0; memset(vis, false, sizeof(vis)); while (!ans.empty()) { ans.pop(); } prog = 0; if (!(BGM_H() == n && dfs(1))) { printf("Case #%d: -1\n",d); }else{ printf("Case #%d:",d); while (!ans.empty()) { printf(" %d",ans.top()); ans.pop(); } putchar('\n'); } } } |
