分支限界法之最小权顶点覆盖问题c++实现
时间: 2023-12-26 18:10:02 浏览: 159
用分支限界法解n后问题
4星 · 用户满意度95%
最小权顶点覆盖问题可以转化为最大匹配问题,而最大匹配问题可以使用匈牙利算法解决。以下是使用分支限界法解决最小权顶点覆盖问题的c++代码示例:
```c++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n, m, ans = INF;
int w[MAXN][MAXN]; // 权值矩阵
int lx[MAXN], ly[MAXN], slack[MAXN]; // 顶标数组
int link[MAXN], visx[MAXN], visy[MAXN]; // 匈牙利算法中的变量
struct Node {
int u, v, w;
bool operator < (const Node& a) const {
return w > a.w;
}
};
void init() {
memset(link, -1, sizeof(link));
memset(lx, -INF, sizeof(lx));
memset(ly, 0, sizeof(ly));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
lx[i] = max(lx[i], w[i][j]);
}
}
}
bool dfs(int u) {
visx[u] = 1;
for (int v = 1; v <= m; v++) {
if (!visy[v]) {
int tmp = lx[u] + ly[v] - w[u][v];
if (tmp == 0) {
visy[v] = 1;
if (link[v] == -1 || dfs(link[v])) {
link[v] = u;
return true;
}
} else {
slack[v] = min(slack[v], tmp);
}
}
}
return false;
}
void KM() {
for (int i = 1; i <= n; i++) {
memset(slack, INF, sizeof(slack));
while (true) {
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(i)) break;
int d = INF;
for (int j = 1; j <= m; j++) {
if (!visy[j]) d = min(d, slack[j]);
}
for (int j = 1; j <= n; j++) {
if (visx[j]) lx[j] -= d;
}
for (int j = 1; j <= m; j++) {
if (visy[j]) ly[j] += d;
else slack[j] -= d;
}
}
}
for (int i = 0; i < m; i++) {
if (link[i] != -1) ans = min(ans, lx[link[i]] + ly[i]);
}
}
void dfs(int u, int cnt, int sum) {
if (cnt >= ans) return;
if (u == n + 1) {
ans = cnt;
return;
}
priority_queue<Node> pq;
for (int i = 1; i <= m; i++) {
if (lx[u] + ly[i] == w[u][i]) {
pq.push({u, i, w[u][i]});
}
}
while (!pq.empty()) {
int u = pq.top().u, v = pq.top().v, w = pq.top().w;
pq.pop();
if (visx[u] || visy[v]) continue;
visx[u] = visy[v] = 1;
link[v] = u;
dfs(u + 1, cnt + 1, sum + w);
link[v] = -1;
visx[u] = visy[v] = 0;
}
dfs(u + 1, cnt, sum);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> w[i][j];
}
}
init();
KM();
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
dfs(1, 0, 0);
cout << ans << endl;
return 0;
}
```
其中,`w[i][j]`表示第i个点和第j条边之间的权值,`lx[i]`表示第i个点的顶标,`ly[j]`表示第j条边的顶标,`link[j]`表示第j条边匹配的点,`visx[i]`表示第i个点是否被访问过,`visy[j]`表示第j条边是否被访问过。`KM()`函数为求解最大权匹配的函数,`dfs()`函数为分支限界法的递归函数。
阅读全文