最小汉密尔顿回路问题状态压缩dp

作者:网络    软件教程库   2020-05-21

给定n个顶点做成的图,要求从顶点0出发经过所有点一次然后回到0点的一条权#20540;之和最小的一条路的权#20540;

#include cstdio
#include iostream
#include algorithm
#include queue
#include stack
#include climits
#include cstring
#include cmath
#include map
#include set
#define inf 100000000

using namespace std;

struct node {
	int end;
	int state;
};
int n,m;
int ma[100][100];
int dp[100][116];


int main(){
	
	while(cin  n  m){
		for(int i = 0;i  m;i++){
			int x,y,w;
			cin  x  y  w;
			ma[x][y] = w;
			ma[y][x] = w;//如果是有向图只要改下这里
		}
		
		queuenode que;
		node s;
		s.end = 0;
		s.state = 1;
		dp[s.end][s.state] = 0;
		que.push(s);
		
		while(!que.empty()){
			s = que.front();
			que.pop();
			for(int i = 0;i  n;i++){
				if(ma[s.end][i]){
					if(!(s.state(1  (i)))){ //这个点之前没有走过 
						dp[i][s.state^(1  (i))] = dp[s.end][s.state] + ma[s.end][i];
						que.push(node{i,s.state^(1(i))});
					}
				}
			}
		}
		
		
		int ans = inf;
		
		for(int i =  1;i  n;i++){
			if(ma[i][0]  dp[i][(1n)-1]){
				ans = min(ans,ma[i][0] + dp[i][(1n) - 1]);		
			}
		}
		cout  ans  endl;
		
	}
	return 0;
}



最小汉密尔顿回路问题 状态压缩dp

原文地址:http://blog.csdn.net/qq_24667639/article/details/45421983

以上就是由(软件教程库https://www.itjcku.com/9999/1091540.html)本站为大家整理

阅读全部内容


Tags:最小汉密尔顿回路问题状态状况

返回首页



推荐内容

POJ1966.CableTVNetwork——无向图的点连通度

http://poj.org/problemid=1966 题目描述: 有线电视网络中,中继器的连接是双向的。如果网 ...

Oracle备忘录1

数据库管理员:安装升级oracle数据库建库,表空间,表,视图,索引。。。制定并实施备份和修复计划数据库权限管理,调优, ...

FileStream文件流

使用文件流拷贝一个较大的多媒体文件: public static void copyfile(string soucr ...

C语言BFS(5)___TT与魔法师(swustoj2464)

description tt生活在一个充满魔法的国度,为了便于管理,国王请魔法师在一些重要的城市之间造出 ...

进程类Process与多线程Thread

进程类(process)的基本操作: //通过进程类查询系统所有进程 process[] pr ...

Xml解析方式之Pull解析器的使用

xml有多种解析的方式,这篇文章只介绍用pull解析器来解析xml文件,接下来我会说明使用pull解析器来读取xml文件 ...

enum,EnumMap,EnumSet

enum基本使用 : package com.enumtest; enum shrubbery { gr ...

Hibernate乱码问题解决

乱码问题其实归根接地就是两端的字符集不统一。 解决思路也有两种: 1. 修改两端字符集统一。 2. 通过代码进行转 ...

eclipse集成struts2.3.20

需要强调的是,这里介绍的是在eclipse工具下集成struts2.3.20而不是myeclipse添加对struts2 ...

ubi文件系统制作,还是"-c"选项的问题

以下是分析记录: --------------------------------------------------- ...

如何把事情做到最好读书笔记1

开篇语: 每个人生来都具备足够的潜力,每个人都能做到别人#30524;中难以企及的事情。请永远保持初学之心,勇敢面对 ...

如何把事情做到最好读书笔记2

第二章 认清自己:你属于哪种类型的人 你必须足够了解你自己,下面有三种类型的人、 (1)浅尝辄止者 浅尝辄止者对一切 ...

如何把事情做到最好读书笔记3

第三章 一份耕耘才能一份收获 当你决定踏上精益求精之路时,你会突然发现周围的一切都与你所追求的#26684;#2668 ...

如何把事情做到最好读书笔记4

第四章 热爱平台期 从小,我们接受的教育就是好好学习,这样才能上好的大学,上好的大学才能找到好工作,有好工作才能有钱买 ...

习题10-21二项式系数UVa1649

1.题目描述:点击打开链接 2.解题思路:本题利用枚举#43;二分解决。问题的关键是选对枚举对象,因为要找c(n,k)= ...

mysql小技巧

selectnow(),user(),version(),database(); #最后输入\c是放弃的意思 des ...

Java学习笔记——面试常客:写出一个死锁的例子

现在的面试挺蛋疼,为了考察大家的语言掌握水平,类#20284;这样的题特别多,不过在某个角度来说确实能看出一个人对某个知 ...

UVA-10396VampireNumbers暴力+打表

题目大意:给出n,要求你输出所有符合规则的n位数 规则如下,这个n位数由两个n/2位数相乘得到,并且满足 1.这n位 ...

CF148D.Bagofmice[概率dp]

题目链接:http://codeforces.com/problemset/problem/148/d 题目大意:一袋子 ...

HDU-1846-BraveGame(巴什博弈)

题目传送:brave game 介绍: 巴什博奕(bash game): 首先我们来玩一个比较古老的报数游戏。a ...

HDU-2149-PublicSale(巴什博弈)

题目传送:public sale 思路:巴什博弈 ac代码: #include lt;cstdiogt; # ...

enum实现售卖机

首先 推荐一下google的代码风格 :https://google-styleguide.googlecode ...

批量添加用户

a、创建用户文件,因为添加的用户比较多,因此编写脚本创建一个用户文件user.txt #!/bin/ba ...

解决侧滑中ViewPager和SlidingMenu的滑动冲突

当我们在使用开源框架slidingmenu时,如果要是使用到viewpager,就会出现滑动冲突。 解决方案: }/** ...

shell打乱文件行

思路,产生一个随机数组,然后按按照数组的元素将文件中行的重新输出 1、随机数组的生成 看书的时候感觉很是简单。第 ...

编程之美2015初赛第二场AB

题目1 : 扑克牌 时间限制:2000ms 单点时限:1000ms 内存限制:256mb 描述 一副不含王的扑 ...

Java设计模式之单例模式(恶汉式和懒汉式)

/* * 单例模式: * 饿汉式:类一加载就创建对象 * 懒汉式:用的时候,才去创建对象 * 面试题:单例模式的 ...

Html简单介绍

1、html--- hypertext markup language 的缩写 --- 超文本 标记 语言. 这个技 ...

configure:error:youmustconfigureinaseparatebuilddirectory

configure glibc-2.14 时出现以下错误: [[email#160;protected] opt]# ...

kohana框架生成feed

创建feed feed::create()斱法用给定癿参数杢创建 rss戒者 atom feed。下面是可接叐癿参数。 ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com