无向图最小权顶点覆盖问题,边没有权值,顶点有c++实现
时间: 2024-01-17 22:02:35 浏览: 31
对于无权图的最小权顶点覆盖问题,可以使用二分图最大匹配求解。具体做法是将图中的点分为左右两个部分,对于每条边 (u, v),在左部分的点 u 和右部分的点 v 之间连一条边,然后求解最大匹配,最小权顶点覆盖即为总点数减去最大匹配数。
以下是使用二分图最大匹配求解无向图最小权顶点覆盖问题的c++代码示例:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int n, m;
int link[MAXN];
bool vis[MAXN];
vector<int> G[MAXN];
bool dfs(int u) {
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
vis[v] = true;
if (link[v] == -1 || dfs(link[v])) {
link[v] = u;
return true;
}
}
}
return false;
}
int maxMatch() {
int res = 0;
memset(link, -1, sizeof(link));
for (int i = 1; i <= n; i++) {
memset(vis, false, sizeof(vis));
if (dfs(i)) res++;
}
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v + n);
G[v + n].push_back(u);
}
int ans = n - maxMatch();
cout << ans << endl;
return 0;
}
```
其中,`G[i]`表示点 i 的邻接表,`link[i]`表示点 i 匹配的点,`vis[i]`表示点 i 是否被访问过。`dfs()`函数为匈牙利算法的递归函数,`maxMatch()`函数为求解最大匹配的函数,最小权顶点覆盖即为总点数减去最大匹配数。