Codeforces Alpha Round #21 D. Traveling Graph(欧拉路,floyed,dp,好题)
发布日期:2021-11-12 00:25:53 浏览次数:12 分类:技术文章

本文共 1743 字,大约阅读时间需要 5 分钟。

D. Traveling Graph
time limit per test
0.5 second
memory limit per test
64 megabytes
input
standard input
output
standard output

You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

Input

The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.

Output

Output minimal cycle length or -1 if it doesn't exists.

Examples
input
3 31 2 12 3 13 1 1
output
3
input
3 21 2 32 3 4
output
14

题意:

给出一个无向带权图,问从1号点出发,通过所有的边至少一次,再回到1号点,需要花费的最少代价是多少。存在自环和重边。

如果无法满足上述要求,那么输出-1。

节点数n,边数m。(1 <= n <= 15, 0 <= m <= 2000)

每条边包含3个属性u, v, w, u和v是边的端点,w是通过边的代价。(1 <= x,y <= n, 1 <= w <= 1e4)。

题解:

先跑一次Floyd求出全源最短路,如果1号点到某个点的最短路不存在那么原图不连通,
如果所有点的度数都是偶数,那么存在一条欧拉回路,已经得到结果,
否则存在某些点的度数是奇数,尝试用一些路径连接这些点,只有路径端点的度数奇偶性会发生变化,
可以发现度数已经是偶数的点作为某条路径的端点是不优的,于是考虑dp[S]表示度数是奇数的点集为S时的最小代价,
转移枚举选出两个集合内的点,用一条路连起来,这两个点的度数都会变成偶数,复杂度是O(n^2*2^n),
一个trick是由于最后所有点度数都要是偶数,也就是每个度数是奇数的点都要作为某条路径的端点,
那么每次考虑选出集合内标号最小的点,枚举这个点和另一个点用一条路径连起来,复杂度是O(n*2^n)。

#include
#include
#include
#include
#include
#include
#include
using namespace std;#define rep(i,a,n) for (int i=a;i
=a;i--)#define pb push_back#define fi first#define se secondtypedef vector
VI;typedef long long ll;typedef pair
PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=18;int g[maxn][maxn],d[1<
0;j--) { for(int i=0;i

转载地址:https://blog.csdn.net/fouzhe/article/details/56482552 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Codeforces Round #176 (Div. 2) D. Shifting(模拟,STLdeque应用)
下一篇:Codeforces Round #399 D. Jon and Orbs(概率dp,好题)

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月07日 19时01分09秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux 离线安装中文字库,centos7 离线安装字体fontconfig 2021-06-24
可以使用鸿蒙系统的55款手机,华为鸿蒙系统首批适配机型即将公布,共有55款产品可升级搭载... 2021-06-24
鸿蒙系统chromeos2.0,【华为鸿蒙系统】鸿蒙OS 2.0 适配计划曝光 2021-06-24
android高德地图设置缩放级别,设置地图中心点/级别 2021-06-24
dv4 安装linux,linux安装中的问题 2021-06-24
gmat阅读.html,GMAT阅读“Ecoefficiency”文章深度分析 2021-06-24
html5 带图片导航,html5 带声音的导航 2021-06-24
point 如何求elbow_机器人学——实践一(Arm Navigation 理论+代码) 2021-06-24
avs3 mkv格式封装_将你的视频无损封装成MP4,非转码哦! 2021-06-24
java http服务端_HTTP协议经典面试题整理及答案详解 2021-06-24
mysql 递归查找父节点_数据结构与算法—浅显易懂的二叉排序(查找)树 2021-06-24
body里写注释 postman_使用 Postman 做 API 自动化测试 2021-06-24
python3的配置文件类单例实现_Servlet是单例还多例 2021-06-24
写一个饿汉单例模式的例子_看完这篇单例模式,终于敢和面试官对线了 2021-06-24
华为手机的分类有何区别_动画有哪些分类?又有何区别? 2021-06-24
编程迷宫_跟我学编程第十期——迷宫游戏 2021-06-24
一键生成安卓证书_【带壳截图+电影台词 生成器】 2021-06-24
北斗轨迹记录_北斗定位+智慧4G视频校车行业解决方案 2021-06-24
存放哪些内容 项目中vuex_房屋安全鉴定中房屋抗震检测内容有哪些 2021-06-24
extjs的panel怎么自适应高度_Ext Js自适应高度 2021-06-24