hdu 5402 Travelling Salesman Problem （技巧，未写完）
2024-09-06 03:32:04
题意：给一个n*m的矩阵，每个格子中有一个数字，每个格子仅可以走一次，问从(1,1)走到(n,m) 的路径点权之和。
思路：
想了挺久，就是有个问题不能短时间证明，所以不敢下手。
显然只要n和m其中一个是奇数，逐行/列绕就可以到达终点，可是恰好都是偶数呢？由于绕不到，那至少得舍弃1个，但是弃哪个比较好？况且有些格子是弃不了的（画4*4的模拟就知道了）。
通过画图可以知道（自己绕！），行号+列号为奇数的格子都是可以舍弃的，而且可以保证其他所有格子都能走一遍到终点（无论是从行/列为单位来绕，这个图都是不变的，即对称）。大概是如下图的圆点都是可以舍弃的：
| O | O | ||
| O | O | ||
| O | O | ||
| O | O |
有一点想不清楚，如果上图中的某个非0格子是将要舍弃的，这可以通过舍弃其他更多的格子来搞定，但是问题是这样做有必要吗？除非所有被舍弃的格子总和都会比上图任意一个0格子要小。但是想一想明白了，若想舍弃这些非0格子中的一个或多个，必须舍弃起码1个以上的0格子，这肯定是不如只舍弃一个0格子更好。
总之，方法就是，扫一遍这些0格子，找出最小的一个，然后在该行之前，全部都是按行来扫，然后对最小格子所在的这两行进行按列扫，绕过它，针对这两行，其入口在左上角，出口在右下角（相当于讲两行压缩成一行，行数变成奇数），接着还是按行来扫，直到(n,m)。最小格子在哪两行？自己搞定（看图）！
代码等补上。。。。。
最新文章
- 简单的学习心得：网易云课堂Android开发第四章服务、广播与酷特性
- VS2010调试速度很慢
- SQL server 2008 Express Edition实现自动备份和自动删除备份
- 802.11 wireless 三
- (转)每天一个linux命令（46）：vmstat命令
- Codeforces Round #219 (Div. 2) E. Watching Fireworks is Fun
- Apache HTTP Server mod_session_dbd 远程安全漏洞(CVE-2013-2249)
- bing翻译API调用方法
- [原创] 利用前端+php批量生成html文件，传入新文本，输出新的html文件
- IBatis.Net 老技术新研究
- Python笔记（一）：安装+爬虫环境配置+打包为EXE文件
- createjs绘制扇形的方法
- Netty 工具类 —— HashedWheelTimer 讲解
- PXE网络启动无人值守自动安装 centos 全程实录
- java news website
- WPF复制异常问题(OpenClipboard 失败 (异常来自 HRESULT:0x800401D0 (CLIPBRD_E_CANT_OPEN)))
- 数据库---mysql的介绍和安装
- Javascript学习笔记5 - 滑动Slides
- Insert Delete GetRandom O(1)
- 关于std::map的第三个参数