[POJ2404]Jogging Trails(中国旅行商问题)(一般图的匹配——状压DP)

时间:2023-01-11 10:07:50

题目:http://poj.org/problem?id=2404

题意:有个n(n<=15)的点和m条无向边,每条边都有自己的权值。现在你要从某个点出发,每条边可以经过多次但要保证每条边至少走一次。现在你要找出一个方案,使得经过所有边的权值和最小,输出最小的权值和。

分析:

首先容易想到的是如果这个图G的每个点的度数都为偶数,那么G是欧拉图,那么一定存在欧拉回路,那么ans=∑每条边权值

如果图G不是欧拉图,那么必有偶数个奇度数的点。

如果我们把每条边都看作有无数条的话,那么原问题就是等价于走一个欧拉回路,也就是在把每条边当作只有一条的边的情况下,将某些边复制若干条,使得成的图G'有欧拉回路且权值和最小。

要把图G加边成G‘,很容易想到其实就是对那偶数个奇度数点进行匹配。既然要最后的边权和最小,那么就可以对偶数个奇度数点重新建图,每两点之间的边的权值定义为图G中两点的最短路径(floyd一下就行),最后用状态压缩dp进行匹配就行了。

[POJ2404]Jogging Trails(中国旅行商问题)(一般图的匹配——状压DP)的更多相关文章

  1. &lbrack;POJ2404&rsqb;Jogging Trails

    我太弱了. 我们可以知道一个结论就是对于一个图的话假如所有点的度数都是偶数,那么只需要走一波欧拉回路. 所以我们就把奇点补成偶点. 将两个奇点补充到偶点的最佳方法是选择任意两个奇点连最短路径为权的边 ...

  2. CodeForces 11D&lpar;状压DP 求图中环的个数&rpar;

    Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no re ...

  3. 一本通 高手训练 1782 分层图 状压dp

    LINK:分层图 很精辟的一道题 写的时候没带脑子 导致搞了半天不知道哪错了. 可以想到状压每次到某一层的状态 然后这个表示方案数 多开一维表示此时路径条数的奇偶即可. 不过显然我们只需要知道路径条数 ...

  4. lightoj 1086 - Jogging Trails(状压dp)

    题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1086 题解:题目就是求欧拉回路然后怎么判断有欧拉回路只要所有点的度数为偶数.那 ...

  5. hdu 4568 Hunter bfs建图&plus;TSP状压DP

    想AC的人请跳过这一段... 题目应该都能读懂.但是个人觉得这题出的很烂,意思太模糊了. 首先,进出次数只能是一次!!这个居然在题目中没有明确说明,让我在当时看到题目的时候无从下手. 因为我想到了这几 ...

  6. HDU 4758 Walk Through Squares &lpar; Trie图 &amp&semi;&amp&semi; 状压DP &amp&semi;&amp&semi; 数量限制类型 &rpar;

    题意 : 给出一个 n 行.m 列的方格图,现从图左上角(0, 0) 到右下角的 (n, m)走出一个字符串(规定只能往下或者往右走),向右走代表' R ' 向下走则是代表 ' D ' 最后从左上角到 ...

  7. HDU 3341 Lost&&num;39&semi;s revenge &lpar; Trie图 &amp&semi;&amp&semi; 状压DP &amp&semi;&amp&semi; 数量限制类型 &rpar;

    题意 : 给出 n 个模式串,最后给出一个主串,问你主串打乱重组的情况下,最多能够包含多少个模式串. 分析 : 如果你做过类似 Trie图 || AC自动机 + DP 类似的题目的话,那么这道题相对之 ...

  8. &lbrack;状压DP思路妙题&rsqb;图

    源自 luhong 大爷的 FJ 省冬令营模拟赛题 Statement 给定一个 \(n\) 个点 \(m\) 条边的图,没有重边与自环 每条边的两端点编号之差不超过 \(12\) 求选出一个非空点集 ...

  9. 状压DP之中国象棋

    题目 传送们 这次小可可想解决的难题和中国象棋有关,在一个N行M列的棋盘上,让你放若干个炮(可以是0个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法.大家肯定很清楚,在中国象棋中炮的行走方 ...

随机推荐

  1. Android 采用HttpClient提交数据到服务器

    在前几篇文章中<Android 采用get方式提交数据到服务器><Android 采用post方式提交数据到服务器>介绍了android的两种提交数据到服务器的方法 本文继续介 ...

  2. 疯狂java学习笔记之面向对象&lpar;七&rpar; - super关键字

    super有以下两大作用: 1.起限定作用:强制去访问父类的成员(Field.方法) 2.起调用作用:指定/显示调用父类的某个构造器 super调用规则: 1.子类构造器总会调用父类构造器一次,默认情 ...

  3. 《TCP&sol;IP 详解 卷一》读书笔记-----IP静态 路由

    1.主机中的路由表只能被守护进程routing daemon或者“redirect”类型的ICMP报文所更新. 2.在根据路由表进行路由选择时,判断的优先级从高到低依次为1)表中存在与目的IP完全匹配 ...

  4. Spring框架入门:(非原著,转载)

    1.1.      耦合性和控制反转: 对象之间的耦合性就是对象之间的依赖性.对象之间的耦合越高,维护成本越高.因此,对象的设计应使类和构件之间的耦合最小. 例: public interface I ...

  5. sql server 锁学习

    insert 默认加的锁是 不允许select,update  但是可以insert update 默认加的锁是 不允许 update 可以 select ,insert

  6. U - 神、上帝以及老天爷&lpar;第二季水)

    Description HDU 2006'10 ACM contest的颁奖晚会隆重开始了!         为了活跃气氛,组织者举行了一个别开生面.奖品丰厚的抽奖活动,这个活动的具体要求是这样的:  ...

  7. HTML的语法

    1,什么是HTML标记语言,他是表示网页信息的符号标记语言,特点包括: a,可以设置文本的格式,比如标题,文号,文本颜色,段落等待 b,可以简历列表 c,可以插入图像和媒体 d,可以建立表格 e,超连 ...

  8. Dynamics CRM日期字段查询使用时分秒的方法

    本人微信公众号:微软动态CRM专家罗勇 ,回复293或者20190110可方便获取本文,同时可以在第一间得到我发布的最新博文信息,follow me!我的网站是 www.luoyong.me . 我们 ...

  9. 1402 后缀数组 (hash&plus;二分)

    描述 后缀数组 (SA) 是一种重要的数据结构,通常使用倍增或者DC3算法实现,这超出了我们的讨论范围.在本题中,我们希望使用快排.Hash与二分实现一个简单的 O(n log^2⁡n ) 的后缀数组 ...

  10. 使用swoole编写简单的echo服务器

    server.php代码如下: <?php class EchoServer { protected $serv = null; public function __construct() { ...