链接:http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3332 本文链接:http://www.cnblogs.com/Ash-ly/p/5454611.html 题意: 给你一个N,代表含有N个点的竞赛图,接着的N * (N- 1) / 2行两个点u, v,代表存在有向边<u,v>,问是否能构造出来一个哈密顿通路. 思路: 竞赛图一定含有哈密顿通路,不一定含有哈密顿回路.则不可能出现不存在的情况,直接构造就可以,至于方法可

链接:http://poj.org/problem?id=1776 本文链接:http://www.cnblogs.com/Ash-ly/p/5458635.html 题意: 有一个机器要完成一个作业,给你一个N*N的矩阵,如果M[i][j] = 1,说明完成第i个作业后不用重启机器,机器可以自动继续去完成第j个作业,否则M[i][j]等于0,则说明如果做完第i个作业,想要继续去做第j个作业,那么必须重启机器.对于每两个作业都有M[i][j] = 1或者M[j][i] = 1.让你求出完成这N个

本文链接:http://www.cnblogs.com/Ash-ly/p/5452580.html 概念: 哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次. 与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关. 判定: 一:Dirac定理(充分条件) 设一个无向图中有N个顶点,若所有

http://acm.hdu.edu.cn/showproblem.php?pid=5424 哈密顿通路:联通的图,访问每个顶点的路径且只访问一次 n个点n条边 n个顶点有n - 1条边,最后一条边的连接情况: (1)自环(这里不需要考虑): (2)最后一条边将首和尾连接,这样每个点的度都为2: (3)最后一条边将首和除尾之外的点连接或将尾和出尾之外的点连接,这样相应的首或尾的度最小,度为1: (4)最后一条边将首和尾除外的两个点连接,这样就有两个点的度最小,度都为1 如果所给的图是联通的话,那

You want to visit a strange country. There are n cities in the country. Cities are numbered from 1 to n. The unique way to travel in the country is taking planes. Strangely, in this strange country, for every two cities A and B, there is a flight fro

Points on Plane Problem's Link Mean: 在二维坐标中给定n个点,求一条哈密顿通路. analyse: 一开始忽略了“无需保证路径最短”这个条件,一直在套最短哈密顿通路的模板,无限TLE. 简单的构造,首先对x坐标设一个阀值,分段输出,从下到上.再从上到下.在从下到上...直到所有点输出完为止. 当然也可横向扫描输出. Time complexity: O(N) Source code:  ;;;;)                  ;}

输入n(1<=n<=6),输出长度为10^n + n -1 的字符串答案. 其中,字符串以每n个为一组,使得所有组都互不相同,且输出的字符串要求字典序最小. 显然a[01...(n-1)]和a[12...n]为相邻组,可以看做有一条边从结点a[01...(n-1)]到结点a[12...n]. 题目转化成求欧拉通路.如果以每组的值为结点,则有10^6个结点,10^7条边.会MLE.(此时其实是哈密顿通路?) 这里以每组的值为边的边权,而边的2个结点分别是前n-1位数和后n-1位数.这样点是10^

我把单词当作点,然后这样其实是不对的,这样就要判定是否是哈密顿通路.. 这题应该把单词的首尾单词当作点,而单词本身就是边,那样就是判定欧拉通路了. 有向图包含欧拉通路的充要条件是:首先基图连通,然后是所有点的入度=出度 或者 有且只有一点出度=入度+1(起点)且有且只有一点入度=出度+1(终点). #include<cstdio> #include<cstring> using namespace std; ]; int Find(int a){ while(par[a]!=a){

目录 DP 四边形不等式 数论 & 数学 数据结构 树链剖分 左偏树的性质及\(O(n)\)的构造 图论 树 二分图 竞赛图 平面图 双连通分量 字符串 后缀自动机 复杂度分析 没什么好写的..(懒得补) 一些博客:http://www.cnblogs.com/GuessYCB/p/9090878.html http://www.cnblogs.com/fenghaoran/p/remember.html DP 四边形不等式 参考 一般对于如下形式状态转移方程:\(f[i][j]=\min\ o

目录 语法 c++ java 动态规划 多重背包 最长不下降子序列 计算几何 向量(结构体) 平面集合基本操作 二维凸包 旋转卡壳 最大空矩形 | 扫描法 平面最近点对 | 分治 最小圆覆盖 | 随机增量法 三维向量(结构体) 三维凸包 几何杂项 数据结构 ST表 单调队列 树状数组 线段树 并查集 左偏树 珂朵莉树,老司机树 莫队 二叉搜索树 一些建议 图论 图论的一些概念 图论基础 最短路径 最小生成树 树论的一些概念 最近公共祖先 联通性相关 图上的NP-hard问题 弦图+区间图 | 最

题目链接: http://codeforces.com/contest/673/problem/D 题意: 给四个不同点a,b,c,d,求是否能构造出两条哈密顿通路,一条a到b,一条c到d. 题解: 构造法,看例子: input: 5 6 5 2 4 1 output: 5 4 3 1 2 4 5 3 2 1 所以只要满足k>=n+1,就可以构造出来答案. #include<iostream> #include<cstring> #include<cstdio>

http://poj.org/problem?id=1776 题意: 有一个机器要完成N个作业, 给你一个N*N的矩阵, M[i][j]=1,表示完成第i个作业后不用重启机器,继续去完成第j个作业 M[i][j]=0,表示如果做完第i个作业,想要继续去做第j个作业,那么必须重启机器 对于任意两个作业都有M[i][j] = 1或者M[j][i] = 1. 求出完成这N个作业启动机器的最少次数,以及每次启动完成作业的数量和这些作业的顺序 初始时机器处于关闭状态. 将M当做图,就是找最少的路径条数覆盖

Children's Dining Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4730   Accepted: 754   Special Judge Description Usually children in kindergarten like to quarrel with each other. This situation annoys the child-care women. For instant,

A(模拟) 题意:求一个特殊图的最大流 分析:画画图发现就是for循环扫一遍 B(LCA) 题意:有n个点组成的树,有q个询问,每个询问(A,B,C),学生从B点走最短路径走到C点,再从C点走到根节点1,问老师从A点出发,能否拦截到学生. 分析: 设u=LCA(A,lCA(B,C)) 那么如果A->u的距离小于从B出发走到u的距离,那么就能拦截 如果距离大于,那么不能拦截 如果距离等于,要判断此点是否在根节点,如果在根节点,那么要判断老师和学生是走一条链上来的还是两条链上来,如果是走一条链上来就

SGU 122 题意:给你n个人,每个人有大于 N / 2(向上取整)的朋友,问你1这个人有一个书,每个人都想看,只能从朋友之间传递,然后最后回到了1这个人,问你 是否有解,然后有解输出路径 收获:哈密尔顿路 一:Dirac定理(充分条件) 设一个无向图中有N个顶点,若所有顶点的度数大于等于N/2,则哈密顿回路一定存在.(N/2指的是⌈N/2⌉,向上取整) 二:基本的必要条件 设图G=<V, E>是哈密顿图,则对于v的任意一个非空子集S,若以|S|表示S中元素的数目,G-S表示G中删除了S中的

建议入门的人先看cd琦的<基于连通性状态压缩的动态规划问题>.事半功倍. 插头DP其实是比较久以前听说的一个东西,当初是水了几道水题,最近打算温习一下,顺便看下能否入门之类. 插头DP建议先理解“插头”的概念.然后会HASH表(这个其实是很基础的东西,应该都会的).然后就是DP. 以及特殊题目的特殊处理. 好像一般是求N,M<=12的网格图的某种回路数或某种通路数的方案数. 大体上每个题说几句特殊处理,有问题请纠正....题目的顺序基本上难度递增 另外代码我都是用括号匹配的.因为感觉连通

题意:给你一个图和每个点的价值,边权值为连接两点权值的积,走哈密顿通路,若到达的点和上上个点相连则价值加三点乘积,求哈密顿通路的最大价值,和最大价值哈密顿通路的条数. 分析:开始看这个题很吓人,但想想这个题状态好确定dp[i][j][k]表示 i已走过点的情况,当前点为j前一点为k所产生的最大价值,枚举所有可行的情况即可,接着想怎么求条数啊, 纠结了好久,才发现和在求价值时若和原来的价值相等,则加原来状态所包含的条数,若更新了最大值,这数量为当前状态的条数,还要注意两条完全反向的路径看成一条路径

题意: 给你一个双向连通图,求 获得权值最大 的 哈密顿通路的 权值 和 这个权值对应的数目: 其中权值计算方法是  列如 ABCD  权值是a+b+c+d+ab+bc+cd 如果 A,B,C  和B,C,D 可构成三角形分别加上abc,bcd: 这个题 和poj 3311  很相像: 那个需要记录一个最后到达的地方   这个需要记录俩个罢了 DP[i][a][b]其中 i  二进制 中1表示这个点走过了   最后走的的 的是b>>a 因为对于已经走过了{1,2,3,4,,5,6,..,N}

题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5418 bestcoder(中文): http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=619&pid=1002 Victor and World  Accepts: 99  Submissions: 644  Time Limit: 4000/2000 MS (Java/Others)  Memory

题目链接:http://poj.org/problem?id=2488 题意: 在国际象棋的题盘上有一个骑士,骑士只能走“日”,即站在某一个位置,它可以往周围八个满足条件的格子上跳跃,现在给你一个p * q的矩形格子,让你找一个跳跃顺序(起点自选),使得这个顺序恰好经过矩阵的每一个格子,且每一个格子仅经过一次,即找一个符合跳跃条件的序列,遍历整个矩形格子.如果有多个,那么就输出字典序最小的. 思路: 貌似可以利用哈密顿通路来解决,但是感觉有点太麻烦,没怎么细想,感觉还是回溯法比较好.首先题目要求