题目大意:有$n(n\leqslant12)$个数,每个数和其他三个数连边,求一个排列,使得边的长度最小

题解:状压$DP$,$f_{i,j}$表示当前确定的数状态为$i$,有$j$条边起点被确定终点没有确定的最短距离

卡点:

C++ Code:

#include <cstdio>
#define maxn 13
int n, m;
int s[maxn][3];
int f[1 << maxn][maxn * 3];
inline int min(int a, int b) {return a < b ? a : b;}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d%d%d", s[i], s[i] + 1, s[i] + 2);
s[i][0]--, s[i][1]--, s[i][2]--;
}
int U = 1 << n;
__builtin_memset(f, 0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < U; i++) {
for (int j = 0; j < n; j++) if (!(i & 1 << j)){
for (int k = 0; k <= n * 3; k++) {
int tmp = k;
if (i & 1 << s[j][0]) tmp--;
else tmp++;
if (i & 1 << s[j][1]) tmp--;
else tmp++;
if (i & 1 << s[j][2]) tmp--;
else tmp++;
f[i | 1 << j][tmp] = min(f[i | 1 << j][tmp], f[i][k] + tmp);
}
}
}
printf("%d\n", f[U - 1][0]);
return 0;
}

  

最新文章

  1. UML(Unified Modeling Language)统一建模语言
  2. css中import与link用法区别
  3. 安卓向服务器发送List数据
  4. Python-requests之POST Data的json问题
  5. 使用CInternetSession CHttpFile下载网页链接地址的文件
  6. UVa 10253 (组合数 递推) Series-Parallel Networks
  7. 安装Hadoop系列 — eclipse plugin插件编译安装配置
  8. SolrCloud 5.2.1 installation and configuration
  9. android 显示特殊符号
  10. codeforces 245H . Queries for Number of Palindromes 区间dp
  11. 【第二篇】Volley的使用之加载图片
  12. [LeetCode] Is Subsequence 题解
  13. 用java理解程序逻辑小结
  14. solr中Cache综述
  15. Vue2 第二天学习
  16. golang显示本机IP代码
  17. maven項目創建紅叉
  18. oo第八次作业--5,6,7次作业总结
  19. HDU 3530 单调队列
  20. Urllib库的基本用法

热门文章

  1. Django---URL、Views
  2. 微信小程序 - 生命周期 - 参数传递
  3. 修改二维码生成插件jquery.qrcode.js支持加入自定义LOGO
  4. pywinauto 使用
  5. angularjs路由不断刷新当前页面
  6. Hadoop(19)-MapReduce框架原理-Combiner合并
  7. 清华大学《C++语言程序设计基础》线上课程笔记01---基础概念与一些注意事项
  8. POJ1679(次小生成树)
  9. 在WPF中自定义控件(3) CustomControl (上)
  10. Error loading MySQLdb module: libmysqlclient.so.18: cannot open shared object file: No such file or directory