最小权顶点覆盖问题
时间: 1ms 内存:64M
描述:
对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖。
输入:
输入数据的第1 行有2 个正整数n 和m(n<100,m<3000),表示给定的图G 有n 个顶点和m条边,顶点编号为1,2,…,n。第2 行有n个正整数表示n个顶点的权。接下来的m行中,每行有2 个正整数u,v,表示图G 的一条边(u,v)。
输出:
将计算出的最小权顶点覆盖的顶点权之和以及最优解输出。第1 行是最小权顶点覆盖顶点权之和;第2 行是最优解xi ,1 ≤i≤n ,xi =0 表示顶点i不在最小权顶点覆盖中, xi =1 表示顶点i在最小权顶点覆盖中。
示例输入:
7 7
1 100 1 1 1 100 10
1 6
2 4
2 5
3 6
4 5
4 6
6 7
示例输出:
13
1 0 1 1 0 0 1
提示:
参考答案(内存最优[2276]):
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 105;
int G[MAX][MAX];
vector<int> bestx;
int w[MAX]; //顶点的权
int n, e; //电路板数,连接块数
class Node {
public:
int dep; //当前层
int val; //所含顶点权值之和
vector<int> x; //解向量
vector<int> c; //边上的另一个顶点
Node() {
for (int i = 0; i <= n; i++) {
x.push_back(0);
c.push_back(0);
}
}
//当前排列长度小的先出队列
bool operator<(const Node &node) const {
return val >= node.val;
}
};
priority_queue<Node> q;
//判断图是否已完全覆盖
bool cover(Node E) {
for (int i = 1; i <= n; i++)
if (E.x[i] == 0 && E.c[i] == 0)
return false;
return true;
}
//添加结点
void addNode(Node enode, int i, int v, bool isLeft) {
Node now;
now.dep = i;
copy(enode.x.begin(), enode.x.end(), now.x.begin());
copy(enode.c.begin(), enode.c.end(), now.c.begin());
if (isLeft) {
now.val = v + w[i];
now.x[i] = 1;
for (int j = 1; j <= n; j++)
if (G[j][i])
now.c[j]++;
} else {
now.val = v;
now.x[i] = 0;
}
q.push(now);
}
int search() {
Node enode;
for (int j = 1; j <= n; j++) {
enode.x[j] = 0;
enode.c[j] = 0;
}
int best;
int i = 1;
int val = 0;
while (true) {
if (i > n) {
if (cover(enode)) {
best = val;
copy(enode.x.begin(), enode.x.end(), bestx.begin());
break;
}
} else {
if (!cover(enode))
addNode(enode, i, val, true);
addNode(enode, i, val, false);
}
if (q.empty())
break;
else {
enode = q.top();
q.pop();
i = enode.dep + 1;
val = enode.val;
}
}
return best;
}
int main() {
// ifstream fin("/Users/SheQiang/Desktop/untitled_folder/MVC.txt");
// cout << "输入图的顶点数:";
cin >> n;
// cout << n;
// cout << "\n输入图的边数:";
cin >> e;
// cout << e;
// cout << "\n输入顶点的权:\n";
int i;
for (i = 1; i <= n; i++) {
cin >> w[i];
// cout << w[i] << " ";
}
// cout << "\n输入每条边:\n";
int a, b;
memset(G, 0, sizeof(G));
for (i = 1; i <= e; i++) {
cin >> a >> b;
G[a][b] = G[b][a] = 1;
// cout << a << " " << b << endl;
}
for (int i = 0; i < MAX; i++) {
bestx.push_back(0);
}
cout << search() << endl;
for (i = 1; i <= n; i++) {
if (i > 1) cout << " ";
cout << bestx[i];
}
cout << endl;
// cout << endl;
// fin.close();
return 0;
}
参考答案(时间最优[32]):
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 105;
int G[MAX][MAX];
vector<int> bestx;
int w[MAX]; //顶点的权
int n, e; //电路板数,连接块数
class Node {
public:
int dep; //当前层
int val; //所含顶点权值之和
vector<int> x; //解向量
vector<int> c; //边上的另一个顶点
Node() {
for (int i = 0; i <= n; i++) {
x.push_back(0);
c.push_back(0);
}
}
//当前排列长度小的先出队列
bool operator<(const Node &node) const {
return val >= node.val;
}
};
priority_queue<Node> q;
//判断图是否已完全覆盖
bool cover(Node E) {
for (int i = 1; i <= n; i++)
if (E.x[i] == 0 && E.c[i] == 0)
return false;
return true;
}
//添加结点
void addNode(Node enode, int i, int v, bool isLeft) {
Node now;
now.dep = i;
copy(enode.x.begin(), enode.x.end(), now.x.begin());
copy(enode.c.begin(), enode.c.end(), now.c.begin());
if (isLeft) {
now.val = v + w[i];
now.x[i] = 1;
for (int j = 1; j <= n; j++)
if (G[j][i])
now.c[j]++;
} else {
now.val = v;
now.x[i] = 0;
}
q.push(now);
}
int search() {
Node enode;
for (int j = 1; j <= n; j++) {
enode.x[j] = 0;
enode.c[j] = 0;
}
int best;
int i = 1;
int val = 0;
while (true) {
if (i > n) {
if (cover(enode)) {
best = val;
copy(enode.x.begin(), enode.x.end(), bestx.begin());
break;
}
} else {
if (!cover(enode))
addNode(enode, i, val, true);
addNode(enode, i, val, false);
}
if (q.empty())
break;
else {
enode = q.top();
q.pop();
i = enode.dep + 1;
val = enode.val;
}
}
return best;
}
int main() {
// ifstream fin("/Users/SheQiang/Desktop/untitled_folder/MVC.txt");
// cout << "输入图的顶点数:";
cin >> n;
// cout << n;
// cout << "\n输入图的边数:";
cin >> e;
// cout << e;
// cout << "\n输入顶点的权:\n";
int i;
for (i = 1; i <= n; i++) {
cin >> w[i];
// cout << w[i] << " ";
}
// cout << "\n输入每条边:\n";
int a, b;
memset(G, 0, sizeof(G));
for (i = 1; i <= e; i++) {
cin >> a >> b;
G[a][b] = G[b][a] = 1;
// cout << a << " " << b << endl;
}
for (int i = 0; i < MAX; i++) {
bestx.push_back(0);
}
cout << search() << endl;
for (i = 1; i <= n; i++) {
if (i > 1) cout << " ";
cout << bestx[i];
}
cout << endl;
// cout << endl;
// fin.close();
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。