# 最小权顶点覆盖问题

``````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``````

``````#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;
}``````

``````#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;
}``````