|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 15;
|
|
|
const int INF = 0x01010101;
|
|
|
|
|
|
int g[N][N]; // 图的邻接矩阵
|
|
|
int n, m; // n个节点，m条边
|
|
|
vector<int> p[N]; // 第一维：哪一行；第二维：此行第几个是哪个点
|
|
|
bool st[N]; // 每个节点是否已使用
|
|
|
int res = INF; // 代价最小值，预求最小，先设最大
|
|
|
int micost[N]; // 每个点最小的代价,相对前一个贪心+暴搜，这个采用了一个估值函数，用于A*寻路
|
|
|
|
|
|
// 现在第u层，讨论k号节点，总共用了cnt个点，现在这棵树价值sum，剩余点的总最小估值代价
|
|
|
void dfs(int u, int k, int cnt, int sum, int r) {
|
|
|
// 最优性剪枝 ！！！最重要！！！只要现阶段不是最小的了就没有继续的必要了
|
|
|
// 假设本层u把剩余的所有节点全部覆盖，那么最小代价根据定义就是r*u,再加上以前积累的sum，
|
|
|
// 总代价就将是sum+r*u,如果此最小代价仍然高于目前取得的小值，那么，此路径无用
|
|
|
if (sum + r * u >= res) return;
|
|
|
if (p[u - 1].size() == 0) return; // 上一层没有选入点（上层为空），树不可能继续构建，该可能不合法，直接跳过
|
|
|
if (cnt == n) {
|
|
|
res = min(sum, res); // 所有点都已经被构建进树中，更新答案，结束这种可能
|
|
|
return;
|
|
|
}
|
|
|
if (k > n) {
|
|
|
dfs(u + 1, 1, cnt, sum, r); // 该层所有点都讨论过一遍，继续下一层
|
|
|
return;
|
|
|
}
|
|
|
if (st[k]) {
|
|
|
dfs(u, k + 1, cnt, sum, r); // 该点已用，直接讨论下一个点
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
// 选用此点（可能1）
|
|
|
int cost = INF; // 找到该点与上层的最小联系(贪心)
|
|
|
for (int i = 0; i < p[u - 1].size(); i++) // 若与上层所有点不连通，则mini是INF,会被最优性剪枝减去
|
|
|
cost = min(cost, g[p[u - 1][i]][k]);
|
|
|
|
|
|
st[k] = 1; // 能算到这里，该点没用过，用下试试
|
|
|
p[u].push_back(k);
|
|
|
dfs(u, k + 1, cnt + 1, sum + cost * u, r - micost[k]);
|
|
|
p[u].pop_back();
|
|
|
st[k] = 0; // 回溯
|
|
|
|
|
|
// 不用此点（可能2）
|
|
|
dfs(u, k + 1, cnt, sum, r);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
memset(g, 0x3f, sizeof g);
|
|
|
memset(micost, 1, sizeof micost);
|
|
|
|
|
|
scanf("%d %d", &n, &m);
|
|
|
while (m--) {
|
|
|
int a, b, c;
|
|
|
scanf("%d %d %d", &a, &b, &c);
|
|
|
g[a][b] = g[b][a] = min(g[a][b], c); // 无向图双向赋值，只取最小值
|
|
|
// 记录接入a,b的最少代价,用于估值
|
|
|
micost[a] = min(micost[a], c);
|
|
|
micost[b] = min(micost[b], c);
|
|
|
}
|
|
|
|
|
|
// 整体最小估值
|
|
|
int r = 0;
|
|
|
for (int i = 1; i <= n; i++) r += micost[i];
|
|
|
|
|
|
for (int i = 1; i <= n; i++) { // 每个点都当一次根
|
|
|
st[i] = 1; // 点已用
|
|
|
p[0].push_back(i); // 根看做第0层
|
|
|
dfs(1, 1, 1, 0, r - micost[i]); // 从第一层开始搜索,考查第1个节点，目前使用了节点个数为1，总代价为0，最小估值为sum-micost[i]
|
|
|
p[0].pop_back();
|
|
|
st[i] = 0; // 以该点为根的数搜索完毕
|
|
|
}
|
|
|
cout << res << endl;
|
|
|
return 0;
|
|
|
} |
