1 条题解
-
1
#include <cstdio> //基础的头文件 #include <algorithm> //给sort开的头文件 #define INF 1917483645 using namespace std; int vis[20], lev[20], d[20]; //vis : 已经访问过的点 //lev : 点距离初始点的距离 //d : 通过此点可以达到的点数 int c[20][20], tar[20][20]; //c : 费用 //tar :存下每个点能到的点 /*为什么要特意存下每个点到的点? 答案其实并不困难,加快访问速度*/ int ans = INF, tmp, tot, cnt, n, m, p; //ans : 最终的答案 //tmp : 最优解剪枝用 //tot : dfs储存中间答案的用具 //cnt :现在已经访问过的点数 //n : 点数 //m : 边数 //p : sort用品 inline bool cmp(int a, int b) { return c[p][a] < c[p][b]; //按照费用给每个点能到的点排序 } inline void dfs(int num, int node) { for(int i = num; i <= cnt; i ++) { //由第几个被访问的点来扩展 if(tot + tmp * lev[vis[i]] >= ans) return; //最优性剪枝,如果当前解加上理论最小的费用都比中途的答案高 //那么这次搜索一定不是最优解 for(int j = node; j <= d[vis[i]]; j ++) //下一步扩展谁 if(!lev[tar[vis[i]][j]]) { //用lev同时充当标记,有lev代表已访问 cnt ++; //多添加一个点 vis[cnt] = tar[vis[i]][j]; //记录这个点 tmp -= c[vis[cnt]][tar[vis[cnt]][1]]; //理论最小的更新 tot += c[vis[i]][vis[cnt]] * lev[vis[i]]; //加上当前的影响 lev[vis[cnt]] = lev[vis[i]] + 1; //因为从vis[i]拓展,故lev一定为其 + 1 dfs(i, j + 1); //继续从i枚举, 注意到tar[i][1 ~ j]已全部访问,下一次从j + 1尝试访问 tot -= c[vis[i]][vis[cnt]] * lev[vis[i]]; //回溯 lev[vis[cnt]] = 0; //回溯 tmp += c[vis[cnt]][tar[vis[cnt]][1]]; //回溯 cnt --; //回溯 } node = 1; //剪枝别剪错了,i枚举玩下次还要从1枚举 } if(cnt == n) { //已经访问了n个点,更新答案 if(tot < ans) ans = tot; return; } } int main() { int u, v, w; scanf("%d%d", &n, &m); //读入n, m for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) c[i][j] = INF; //初始赋无限大,方便后面的操作 for(int i = 1; i <= m; i ++) { scanf("%d%d%d", &u, &v, &w); //这个w先暂时存起来 //因为发现m = 1000 远> n * n,所以要剪掉一些边 if(c[u][v] < w) continue; //w不能更新c[u][v] if(c[u][v] == INF) //第一次更新c[u][v],统计u,v的出度 tar[u][++ d[u]] = v, tar[v][++ d[v]] = u; c[u][v] = c[v][u] = w; } for(int i = 1; i <= n; i ++) { p = i; //sort排序cmp sort(tar[i] + 1, tar[i] + 1 + d[i], cmp); tmp += c[i][tar[i][1]]; //因为每个点总要扩展一条边, //因此我们把最小的边找出来,作为最优性剪枝 //不仅如此,因为边越小作为最终解的可能性越大 //实际上在一定程度上优化了程序 } for(int i = 1; i <= n; i ++) { tot = 0; cnt = 1; //赋初值 vis[1] = i; //第一个就选i tmp -= c[i][tar[i][1]]; //i的最优性剪枝的影响要去掉 //因为剪枝的时候是以还未访问和还未将被访问的点为基础的 //不去掉剪枝就是错误的 lev[i] = 1; //赋值 dfs(1, 1); //只有一个点,也肯定是从1枚举 lev[i] = 0; //回溯 tmp += c[i][tar[i][1]]; } printf("%d", ans); return 0; }
- 1
信息
- ID
- 75
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 12
- 已通过
- 7
- 上传者