从特殊的图论模型谈开去

最近停课集训算是让我短时间内也接触了不少图论模型,再加上之前的,够我写一篇文了。

在这篇里面我并不想谈关于 弦图,区间图,PQTree,完美消除序列 以及那篇文留下的几个大坑,我想从几个比较常用的和比较具有启发性的小玩意说起。

 

 

 

 

 

 

 

 

斯坦纳树

我是在做 [JLOI2015]管道连接 的时候学习到 Steiner Tree Problem 的。这个东西是什么呢?

我们看一下背景……


背景

Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.


斯坦纳树问题 (STP) , 或者说最小斯坦纳树问题, 是一类 组合优化 问题的统称, 那么尽管这个问题可能被设定到许多环境中, 但它都是一类要求: 对于给定的一个对象集合和一个预先定义好的作用于对象的函数, 求出集合的最佳互联的问题.

我们常用的 Steiner Tree Problem 的一个同义指的是在上的 STP . 也就是给定一个非负权边的无向图 和一个顶点的子集 ( 这些给定的顶点通常被称为 terminals ) , 那么我们要求一个把 terminals 联通的最小权生成树. (虽然这个生成树可以有非 terminal 结点).

还有一些奇怪的变种比如 Euclidean Steiner tree problem 和 rectilinear minimum Steiner tree problem.

(这个翻译我真的尽力了.)(我再翻译一些)

这个问题可以说是(非负权的)最短路问题和 MST 问题的组合. 那么如果只有两个 terminals , 它显然是一个最短路问题. 如果所有的结点都是 terminals , 它则是一个 MST 问题.

虽然最短路问题和 MST 问题都是 P 问题, 他们的好哥们 Steiner Tree Problem 却是一个 NPC 问题! 但是虽然大多数 STP 都是 NP-hard 的, 但在某些限制条件下它可以在多项式时间内解决.


PollakGilber猜想

Pollak-Gilbert 猜想指出,平面上任意 n 点集,斯坦纳最小树长与最小生成树之长的比值的最小值是 \frac{\sqrt{3}}{2}


求解问题

子集DP。把 j 的二进制各位的 0/1 看做集合中各个元素选/不选,那么可以设计状态 dp[i][j] 来表示以 i 作为根, 并且集合选择状态为 j 的情况下的最优解答。

转移分两步:

  • 先通过对 j 进行划分求得对于 i,j 下的最优解。
  • 再通过 i,j 去优化 j 下的其他根的答案。

为什么只优化 j 下的呢?因为其他联通状态会转移到 j 或由 j 转移得到。

第一种转移:

除了枚举子集去更新之外,不要忘记要把有效状态放入队列。

第二种转移:


复杂度分析

我们枚举子集的复杂度应是 n \times \sum (C_k^i \times 2^i) = n \times 3^k

那个 SPFA 的复杂度是 n \times 2^k

那么就是 O(n \times 3^k)


流程回顾


Advanced: 斯坦纳森林问题

并没有多大难度。

考虑这样一件事情:我们给定并非一组 terminals ,我们给定 k 组。

对于这 k 组 terminals ,我们只要求同组中的是互相联通的。求一个生成树的最小花费方案。

那么我们可以这样:

我们枚举一个状态 w , 然后我们把 w 二进制拆分对应的几个集合中的 terminals 看成一组 terminals 。然后去做 STP。

然后我们求全集的答案就是再次子集DP一遍:

就很简单做完了。


图的遍历问题

这个问题比较有来头,他牵涉到了图论的起源(或者说创生?)

背景是著名的所谓 Könisberg seven bridge problem ,相信大家都已经耳熟能详了。

由此我们诞生了 Euler 回路或者说, Euler 环游问题。

那么现在我们来看另一个更难的问题: the Chinese Postman Problem (CPP)

(注:下文顶点和结点混用,但其实是一回事,vertex or vertice)

 

一些记号

环游就是从结点 v_0 出发最终回到 v_0 的一个有序路径。

在一个无向正权图上,经过每条边至少一次的环游的权是经过边的权值与次数的乘积的和。

即: v_0e_1,v_1e_2,\cdots ,e_nv_0 的权为 \sum_{i=1}^{n} w_{e_i}

图的最优环游就是该图的最小权的环游。

 

问题描述

那么这个问题是这样被描述的:

给定一个无向正权联通图,求出最优环游。

 

求解

第一,如果图是一个 Euler 图,那么显然任意一个 Euler 环游都是一个最优环游。

第二:非 Euler 图

把这个图记为 G

我们使用一种方法就是重复边法,说白了很简单,我们先假设答案已经求得,我们先规定每条边只能经过一次,然后把答案中重复的边拆成多条边,在原图上画出。

记这个新图为 G' ,这个 G' 显然是一个 Euler 图。

那么我们的任务就是构造出这样一个 Euler 图 G' 并且让它添加的边(称为重复边)的边权总和 W 最小。

 

Edmonds-Johnson 算法

case 1: G 正好有两个奇次(度)顶点

记这两个顶点为 S,T ,跑最短路即可。

case 2: G2n 个奇次顶点

我们使用 Edmonds 最小对集算法

思想:就是把 case 1 推广到了多组顶点上。

先用随便什么方法求出所有奇次顶点之间的最短路。 (Floyd or Dijkstra)

然后以这些奇次顶点为点集,做一个完全图,边权是两点间最短路。该图记为 G_1

我们跑带花树求出 G_1 的最小权完美匹配。(取负跑最大权完美匹配)

然后就做完了。

case 3:其余情况无解

 

注: 带花树写的只要不丑,差不多110行多点(含头文件IO等)。

注:我不会写。


2-SAT问题

缓更,但今晚肯定会更。

 

 

JLOI2010 世界杯租房

数据很水,偷偷看了下好像 T \leqslant 100

嗯,DP+输出方案。记得为了字典序最小我们要倒着DP。。

然后没了。。别写龊了写炸复杂度就好。

O(Tmn^2)

 

 

JLOI2008 CODES

一天半,唉。。真该AFO了。

首先考虑我们可以DP,设状态 dp[i][j] 表示 第 i 个字符串  还需要匹配长度为 j 的前缀   可以得到的最短答案。

转移:

转移就是枚举一个字符串 i_0 来与之匹配。记忆化搜索非常好写。注意讨论两种情况:

  1. i_0比当前前缀长
  2. i_0比当前前缀短

用 dp[i0][?] + 匹配长度 去更新dp[i][j]。(?是因为我懒得讨论了……代码里有)

数据范围很小,暴力匹配即可。

注意事项:

第一个细节就是字符串可以重复利用;

第二个细节是让dp[i][0]=0 其余为 +\infty

第三个细节就是最后统计答案和DP过程中别忘记比较字典序。

字典序:

 answ[i][j] 保存当前 dp[i][j] 对应的具体方案,

更新 dp[i][j] 顺便更新 answ[i][j] 即可。

每次遇到 dp[i0][?]+len  dp[i][j] 相等的情况,判定字典序,然后更新 answ[i][j] 即可。

最后的答案是 dp[i][len[i]]

O(\text{跑得过})

[JLOI2009]F1一级方程式大赛

……NOIp提高组难度,hhh

首先这是一道DP……这很显然。。

注意到每次加油一定是加刚好够跑整数圈的油……要不浪费时间。

然后方便起见,我们预处理跑 1 \sim n 圈的耗油和耗时,因为这和你当前在跑哪一圈是无关的。

设为了跑第 i 圈,需要用油 q_i ,每圈空车跑油 s   , 每多一升油多跑油 a , 初中数学解方程可以得到:

q_i = (q_{i-1} + q_i) \cdot a + s

q_i = \frac{s + q_{i-1} \cdot a }{1-a}

时间比较好算……就不说了。

预处理完了,我们开始dp。

设dp[i][j]表示:在第 i 圈起点,准备不加油一口气地跑 j 圈的最小时间。

转移就是(need是跑 i 圈的油量,tim是时间,incost是进加油站,gcost是加油):

然后记录一下转移的前驱,最后输出就行了。

O(n^3)

 

头插DP指北

UPD:排版已挂。先去洛谷看吧,这边待修。

洛谷ID:GNAQ

 

UPD:我稍微改了一下封面图片,现在它成了真 · 插头DP了 😕

插头DP的概念(据我不可靠考证)最早出现在08年CDQ的论文中,而此类题目早在04年前后就已经存在。

(***下面假设聚聚们都会了状压DP……)


1.什么是插头DP

插头DP (PlugDP ,By yhzq),也就是一类基于连通性的状态压缩动态规划,是用状压DP处理联通问题的强劲武器。

常见的类型有棋盘插头DP和CDQ论文里的两个非棋盘上的模型。

常见的联通问题:多回路问题、路径问题、简单回路问题、广义路径问题、生成树问题


2.插头DP的大致思路


2.1 划分阶段

大家都知道了这是基于联通性的状压DP,所以本质上还是状压DP。

一般设dp[i][j][state](i,j)位置,状态为mathrm{state}的方案数(或者代价,等等让你求的东西……)

所以我们状压什么呢?轮廓线。

DP求解棋盘问题是逐格转移的。所以已经转移过的格子和没转移过的格子被一个折线分成了两半儿。这个折线就是轮廓线。

@远航之曲的简洁解释:已决策格子和未决策格子的分界线)

就这个蓝线(现在转移的格子是第3行第3个)。

插头又是什么呢?一个格子有四个插头,一个存在的插头表示在它代表的方向上能与相邻的格子连接(联通)。不存在就不能。

为什么要引入插头?要求一个回路,也就意味着最后所有的非障碍格子通过插头连接成了一个连通块,因此转移时需要记录格子的连通情况。

我们递推的时候就是依据轮廓线上的插头存在性,求出所有能转移到的合法状态

显然回路问题中一个格子恰好有两个插头,一个是“进来”的一个是“出去”的。


2.2 记录状态

最小表示法

所有的障碍格子标记为 0 ,第一个非障碍格子以及与它连通的所有格子标记为 1 ,然后再找第一个未标记的非障碍格子以及与它连通的格子标记为 2 ……重复这个过程,直到所有的格子都标记完毕。比如连通信息((1,2,5),(3,6),(4)) 表示为{ 1,1,2,3,1,2 }

(还有一种最小表示法,即一个连通块内所有的格子都标记成该连通块最左边格子的列编号。)

括号表示法

【性质】轮廓线上从左到右 4 个插头 a, b, c, d,如果 a, c 连通,并且与 b 不连通,那么 b, d 一定不连通。这个性质对所有的棋盘模型的问题都适用。证明详见CDQ论文。

“两两匹配”,“不会交叉”这样的性质,我们很容易联想到括号匹配。

将轮廓线上每一个连通分量中左边那个插头标记为左括号,右边那个插头标记为右括号,由于插头之间不会交叉,那么左括号一定可以与右括号一一对应,这样我们就可以使用 3 进制, 0 表示无插头, 1 表示左括号插头, 2 表示右括号插头,记录下所有的轮廓线信息。不妨用#表示无插头,那么上面的三幅图分别对应的是 (())#(),(()#)(),(()###) ,即 (1122012),(1120212),(1120002) ,这种表示方法称为括号表示法。

状态的编码

对于最小表示法,编码最简单的方法就是表示成一个 n+1 位的 p 进制数, p 可以取能够达到的最大的连通块标号加 1 。在不会超过数据类型的范围的前提下,建议将 p 改成 2 的幂,因为位运算比普通的运算要快很多。

如需大范围修改连通块标号,最好将状态 O(n) 解码到一个数组中,修改后再 O(n) 计算出新的 p 进制数,而对于只需要局部修改几个标号的情况下,可以直接用 (x ;mathrm{div}; p^{i-1} ) ;mathrm{mod}; p 来获取第 i 位的状态,然后 +k times p^{i-1} 直接对第 i 位进行修改。


2.3 转移状态

首先,因为逐行递推要讨论的情况还是比较难处理的,除非要求解的问题特别适合这样做,要不然我们一般使用逐格递推,这样可以方便讨论情况。

一般来说轮廓线上有不少状态都是无用的,而且一般来说插头DP的状态数很多,所以我们使用一个技巧来加速,那就是,我们用一个线性数据结构(我愿意开一个/模拟一个vector)来存储状态,每次读取上一格的所有合法状态扩展,而不是xjb枚举状态来扩展。

然后,我们来研究一下怎么转移。我们看一种题型吧。

给你一个 m times n 的棋盘,有的格子是障碍,问共有多少条回路使得经过每个非障碍格子恰好一次。

m, n \leqslant 12

1.新建一个连通分量

这个情况只出现在转移位置的轮廓线上没有下插头和右插头。

如图。然后我们只有一种转移方式就是当前格做右插头和下插头。

括号表示法就是新建一对紧挨着的左右括号。最小表示法就直接解码重编一下。

2.合并两个连通分量

如果当前轮廓线上既有右插又有下插,那你只能当前格做左插和上插,要不然就不是回路了。

然后如果右插和下插联通,那这种情况只能是在最后一个非障碍格是合法的。

不连通的话,当然这样做会把他们变联通,看图:

括号表示法里就直接删一对括号,最小表示法还是解码重编。

3.保持原来的连通分量

当轮廓线上只有下插或者右插,就只能当前格做一个左插/上插来满足回路性质,剩下一个插头是随便安排的。

图:

括号表示法的话就把下插/右插对应的括号移到你加的插头上就行了。

最小表示法也类似,把下插/右插位置的记号移到你加的插头对应位置就行(因为是延续了一个连通分量)。

注意当从一行的最后一个格子转移到下一行的第一个格子的时候,轮廓线需要特殊处理。这个看代码最好解释了。

(还要多啰嗦一句,一般状态编码的左右和轮廓线的左右是反着对应的……也就是编码最右面一位是对应轮廓线最左面格子)

一个小优化

有时候你转移的时候有可能从两个不同状态转移出同一个状态,这个时候我们用hash优化它就好了。hash表的实现用挂表法就行。

还有提取每个插头状态的时候我们可以预处理一个对应bit的数组,然后用上文提到的解码方式去解码。

这儿还是曲神@远航之曲的trick,他讲的很明白。


然后我们就讨论完了插头DP的第一道入门题该怎么做,题目提交在这儿:1519. Formula 1

我真的是抄的曲神的代码,曲神码风和实现都太棒了!


··
·····


state是表示状态,dp表示方案数。这里用了滚动数组来优化空间(pre,cnt来滚动)


bits是一个方便提取插头的数组。比如bits[3]=6,那提取第三个格子上面和左面的插头(分别叫做is_d和is_r)就是state>>bits[3-1]和state>>bits[3]


我们存储状态是四进制,括号表示法。1表示(,2表示) 。


hash表的内部实现你可以看到就是一个链表。(struct hash_table)


·····


因为可能最后一格也有障碍,所以要记录一下最后一个无障碍格子(endx,endy)


··


添加状态压进hah()函数里了。


·

·

·····


一开始要初始化dp(0,0)=1


·


77行,这是为了转移到下一行的时候处理第一个格子的is_r插头(建议在纸上模拟一下)


····


case 0:有障碍。

case 1:

case 2:

case 3:

case 4:(要改插头)

case 5:(要改插头)

case 6:(要改插头)

case 7:形成一个回路。只有最后一个格子才能形成一个回路。

P.S.为了做上面那个效果我拿Elementary Editor搞了半小时……

To be continued……

再来一道毒题 P3886 [JLOI2009]神秘的生物

唉。这题我写了差不多四天……还是真的菜。

首先说明的是这份代码来自vawait大佬 (肽聚了,写了无数插头DP……)

这道题还有一个很有意思的背景:

仔细想想你会发现SRM312好像是06年的比赛……

JLOI居然抄原题,差评

还有就是其实经过我的深刻反思,我意识到……

原题卡好几天!……

唉 我应该把论文和课件都看一遍的TAT

有一种策略就是我们可以只转移有左插和上插的格子。可惜其实这是很不对的一个策略,你没法应付像这样:

真令人头秃。那怎么办呢? 🙄

一些注意事项

首先你会发现,因为四个插头都是本质相同的,所以我们大可以用一个插头去概括它,也就是说,本题所谓的轮廓线是这样的:

也就是我们只需要保存 n 个格子的最小表示就可以转移了。稍加分析可以得到我们需要八进制来表示这么多格子的最小表示。


转移状态

按照一贯的套路我们又要讨论如何转移状态。基于对联通信息的维护,我们会有:

1.当前格无插头

2.当前格有插头

2.1 当前格属于“新建一个联通分量”

2.2 当前格加入之前的联通分量

所以一共有三种转移。

1非常好做。去掉即可。

2.1 非常好做,我们可以用 7 来表示新建的联通分量

2.2 从vawait大佬那里看到了一个实现上的技巧就是让当前的最小表示等于 mathrm{max(Dplug,Rplug)} 。然后让所有最小表示为 mathrm{min(Dplug,Rplug)} 的也等于它。


判定状态合法性

这个题和之前的不一样,因为答案并不是最后更新,转移完之后状态也都不一定是合法的。

所以hash之前应该先判一下状态的合法性

1如果没有下插,或者下插(也就是当前格的上面一格)与轮廓线上其他格联通,那这样转移是合法的,反之一定不合法。

2.1和2.2是一定合法的。


更新答案

hash之前要重新编码,编码完之后如果当前轮廓线上有一个或零个联通分量都是满足题目要求的状态,可以更新答案。


hash

还是和之前一样。不过我从vawait的代码里get到一个卡空间的技巧,就是把dp状态也压进hash表里。感觉也不难写。


重新编码

思路还是挺简单的。唯一需要合并联通分量的地方2.2也已经提前处理好了。

#洛谷 P1860 新魔法药水

神奇的DP

大概是用DP预处理要预处理的内容

然后用DP预处理

最后DP背包跑答案

 

卡了我很久有必要详细讲一下

题目描述

商店里有N种药水,每种药水都有一个售价和回收价。小S攒了V元钱,还会M种魔法,可以把一些药水合成另一种药水。他一天可以使用K次魔法,问他一天最多赚多少钱?

输入输出格式

输入格式:

第一行四个数N、M、V、K

接下来N行,每行两个数,表示药水的售价和回收价。

接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号

输出格式:

一个数,表示小S的最大利润

·

N<=60 M<=240

V<=1000

k<=30

我们先考虑这是个背包

然后很自然的只需要求每个物品的min 购买价,然后二位费用xjb转移就可以得出答案

DP求这个部分.

因为有魔法,所以设计状态dx[i][j]表示物品i在当前用了j次魔法的情况下最小的购买价,这样才能当做背包来DP

dx怎么求呢?也不好求,所以这就是卡我的地方,我一开始还以为是DFS求

 

厚颜无耻的看题解……

你需要在枚举每个魔法w的时候都dp处理出 第w个魔法所需的前x个物品 用y次魔法 可以得到的最小购买价

设计状态ori[x][y]表示这样,每次枚举了一个魔法w都要求一次ori,注意y≤枚举的魔法次数

然后DP一波ori,这个很简单,写过几道提高水平的DP就会求

然后用ori[w需要的物品总数][枚举魔法次数-1]更新dx[w产成品][枚举的魔法次数]

·

这样我们就有了dx

xjb背包即可.XXXD

NOIp2017 DP专项练习

1 Power收集

设dp[i][j]为走到第i,j个位置的最多能量,考虑每一个状态都从上一层dp[i-1][j-t ~ j+t]转移而且取max,于是简化状态每一次用堆维护上一层的最大数(std应该是单调队列然而时限比较善良于是堆也能水过)然后检查当前位置和堆顶元素位置,不满足就pop。然后取堆顶转移

关路灯

区间……没做出来看题解了……

设dp[i][j][0/1]表示把区间[i,j]内的所有灯全部关闭并停在i(第三维是0)或j(第三维是1)处,已经消耗的电能

枚举区间大小转移。注意dp[i][j][0]可从dp[i+1][j][1]转移来,dp[i][j][1]能从dp[i][j-1][0]转移来

小a和uim之大逃离

脑残没想到看题解系列

知道状态一定有第四维,也知道一定有前两维……然而就是脑残想不到可以化成O(nmk),还傻傻的以为是O(n2m2)……

只允许这一次脑残了……

我们设dp[i][j][p][0/1]表示从1,1用随便什么路径走到i,j点,并且disA-disB=p(%k意义下,所有没有负数,尽管应该有)时的合法方案数

那就是dp[i-1][j][ ( (p-mapx[i][j])%k +k)%k ][1]+dp[i][j-1][ ( (p-mapx[i][j])%k +k)%k ][1]

(逆序还原上一个状态的p,因为现在是A走达到了p,那么没经过i,j之前一定是p-mapx[i][j])

另一个状态同理。

注意随时%1000000007

最后O(NM)统计答案。

 矩阵取数游戏

本质上就是关路灯

套一个高精度就行了

我设的dp[i][j]表示这一行余下区间[i,j]的时候的最大得分(好像是得分?还是什么……?)

每一次从dp[i-1][j]+pow(2,m-(j-i)-1)*mapx[i-1][j]和dp[i][j+1]+pow(2,m-(j-i)-1)*mapx[i][j+1]取max转移

注意最外面一层是从大到小枚举长度

最长公共子序列(LCS问题)

傻比题既视感

大概是这样:因为是一个排列,考虑把B串做一个映射,标记下每一个元素(1~n)在B串中的下标

然后让A串通过映射构造一个新的串,因为是公共序列问题,所以只要在新串中按照顺序出现的就是A与B重合的。

比如说,6在B中是[19],那就把6映射到19(codex[6]=19)            3在B中是[22] 也映射过去

那么假设6在A中是[2]那么新串C[2]=codex[A[2]]       所以C[2]=19

3在A中是[5],那么C[5]=codex[A[5]]      C[5]=22

那么显然在A串中,3在6后面,而且B串中3也在6后面,这样如果把A中3 6替换为3 6在B中的下标,那一定是递增的。

最后nlogn做法的LIS就可以过

有线电视网

关键词:树上背包,傻比题。

设状态f[i][j]表示结点i连接j个用户的最大赚取(支付的钱-花费)然后枚举子树暴力转移一波就行

注意计数,枚举到一颗新的子树,现在结点的[最大连接用户(叶子)数目+=子树的最大连接数目]
然后j从0循环到最大连接数目取max

dp[nownode][i] = max ( dp[nownode][i] , dp[nownode][i-j] + dp[v][j] – edge[prex].w );

加分二叉树

破区间dp,什么玩意

对于每个子树,枚举它的根节点(>=L <=R)然后暴力dp更新

1.设计状态dp[i][j]表示在中序遍历中i~j这段区间代表的子树的最大加分

2.注意空树的处理 if (i>j) return 1;

[HAOI2012]音量调节

傻比题,纯粹是为了有时间tuifei

然而交了三遍才过,变量重名竟然都检查不到。

就是些**样例 -Yansir

[HAOI2009]逆序对数列

看题解才过去……

真是道好题

设dp[i][j] 表示前i个数(1-i)出现j个逆序对有多少方案,可知dp[1][0]=1;

考虑把第二个数分别放在第0个位置(第一个数之前),第1个位置,第2个位置……假设现在的i=2则有dp[2][2]=dp[1][2]+dp[1][1]d+dp[1][0]

也就是分别放在哪个位置上(0,1,2  ps注意前后括号里的对应),还欠缺的逆序对需要用之前的i-1个数补。(dp[1][0] dp[1][1],dp[1][2])

归纳总结一下:

1.dp[i][j]=∑dp[i][k]         (  max(j-i+1,0) ≤ k ≤ j  )

2.用前缀和优化转移,O(n2)

直接令dp[i][j]代表之前的∑dp[i][k]    (0 ≤ k ≤ j )

然后转移可以O(n2)  :      dp[i][j]=dp[i-1][j]-dp[i-1][j-i]   +dp[i][j-1]

10 跳舞

(背景)很像紫书上的那个Tango

设计状态dp[i][j]表示踩到了第i个箭头的时候踩了j次,此时的最大得分

可以发现决策就两个:踩,得分;或者不踩,扣分。

所以从dp[i-1][j-1]+socre[i] , dp[i][j]-score[i]转移

特判j%t=0的情况,此时踩多加分,不踩不多扣分

11 

JZOJ 3808 | Luogu2103 道路值守

题目描述

Z-Kingdom有着四通八达的现代化交通。时值独立庆典之际,随着来自周边国家旅客的日益增多,犯罪行为也悄无声息开始滋长起来。

特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查,他们得到了一张地图,记载了Z-Kingdom内每一条道路的长度。

显然,为了减少犯罪行为被发现的可能性,犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线,他们希望得知任意两个地点之间,有多少条犯罪分子可能会选择的道路。

输入输出格式

输入格式:

第一行,包含两个整数N,M,表示Z-Kingdom内的地点数和道路数。

接下来N行,每行包含三个整数x,y,z,表示道路连接的两个不同地点的标号,以及道路的长度。道路是双向的。

两个不同地点之间不会有超过一条道路。

输出格式:

输出一行,包含 N (N-1)/2 个整数

其中表示 x 号地点到 y 号地点之间有多少条犯罪分子可能会选择的道路。

先Floyd求出最短路

对于每一个点i:

{

枚举所有点j ,确保i,j联通,且i,j不是一点。

然后检查有多少点k与j有连边,且在i-j的最短路disi,j上。(也就是检查从i到j有多少条满足disi,j上且与j相连

       esumj=∑k1     k∈(g[k][j]!=0 && dis[i][k]+g[k][j]==dis[i][j])

最后考虑DP

枚举一个终点j,再枚举一个k,如果k在i-j的最短路上,那么esum[k]个方案计入C[i][j]。(有esumk条边可以到k点,在最短路上可以选k点,所以要计入方案数目)

}

BZOJ1924 | SDOI2010 所驼门王的宝藏

在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状,由R×C间矩形宫室组成,其中有N间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔,由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门,没有宝藏的宫室不设传送门,所有的宫室传送门分为三种:

  1. “横天门”:由该门可以传送到同行的任一宫室;
  2. “纵寰门”:由该门可以传送到同列的任一宫室;
  3. “自由门”:由该门可以传送到以该门所在宫室为中心周围8格中任一宫室(如果目标宫室存在的话)。

深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册,书册上详细记录了每扇传送门所属宫室及类型。而且,虽然宫殿内外相隔,但他自行准备了一种便携式传送门,可将自己传送到殿内任意一间宫室开始寻宝,并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次,且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制,每间宫室也可以多次出入。

现在Henry已经打开了便携门,即将选择一间宫室进入。为得到尽多宝藏,他希望安排一条路线,使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。

 

[无耻地借用洛谷的图片]

首先缩一下点……

然后跑DP……

很简单QAQ

在BZOJ写了7000B,成功拿到『最近几页的最长代码』成就

在洛谷跑了400ms,超级快。//好像空间还用的很少