hdu6007 Mr. Panda and Crystal dij+完全背包

我们只要求出每种宝石获得的最小花费,这道题就变成了完全背包。

我们回顾下方程 dp[v] = max(dp[v],dp[v – c[i]] + p[i]) v从1开始循环。

然后怎么求出每种宝石获得的最小花费呢?

我们回顾下题意,发现模型有些类似最短路,只不过每个点的dis是组成成[……]

Read more

hdu 6393Traffic Network in Numazu 基环外向树 LCA 树

题意就是,给你一个基环外向树,然后问任意两点间最短路,有修改边权,nlogn做法。

然后就在环上随便删一个遍,然后我们lca求最短路,再看经过删掉的边的距离,取个min就好了。这题数据很有趣,最后一条边一定在环上,可以少写一个dfs……

然后怎么修改边权,线段树按照dfs序维护一[……]

Read more

luogu P3385 【模板】负环 SPFA

有点迷茫 ,DFS似乎快的点特别快,慢的点特别慢。BFS似乎都不怎么快,那似乎上限低点,不知道该用哪个。。

BZOJ 1202: [HNOI2005]狡猾的商人 差分约束 spfa

差分约束,有空再详细讲

//之前的写法有问题,数据水,直接过了,需要建一个超级源保证联通才行,否则与0点不连通的负环会不被考虑。

bzoj 2007: [Noi2010]海拔 平面图最小割

貌似是近似网格图,spfa跑到慢,会TLE2个点。需要用堆优dij。

这题建图折腾了一个晚上。今早才整明白,quq。。。

第一,左上角是0,右下角是1。那你左下角是s,右上角是t。

第二,所有边都应旋转一个统一的角度。

第三,这个角度不能随便钦点是顺90,还是逆90,手测个小[……]

Read more

bzoj 1486: [HNOI2009]最小圈 spfa判负环

二分答案,然后每条边边权减去这个值,然后判负环。

bzoj 1295: [SCOI2009]最长距离 spfa

一眼切,代码码半年。

对于网格图重新建图。从一个点出发,四联通,走向一个障碍物,则边权1,否则边权0。然后对于每个点跑spfa,然后判断更新答案即可。注意以一个障碍物为起点,则会额外花费一个消除的步数。

我tm再把dis数组开成bool类型!!!!我就吃**********。
[cra[……]

Read more

ACM 训练 POJ 3592 Instantaneous Transference 强连通分量

给你一个网格图,内部有一些联通关系,然后一些点有一些点权,一个点权最多得一次,问获得最大点权。先强连通缩一下点,然后跑最长路就可以了。

bzoj 2763: [JLOI2011]飞行路线 spfa 分层图

T的要死要活,卡常无果。然后感觉分层图是不是我先优先扩展本层,把本层扩展到最优然后再向其他层扩展,反复的松弛操作会少一些。然后我选择优先扩展本层,然后就A了。7000多ms。看网上题解,也是这么做,为什么他们这么快,几百毫秒就过去了,quq。。。

就dis[u][k]表示用k次免费机会到dis[……]

Read more

bzoj1003 ZJOI2006 物流运输 dp + spfa

这题数据范围很小,我们可以任意瞎搞。首先我们先考虑有这么一个数组cnt[i][j],表示[i,j]这些天保持同一计划每天运输的最小代价。(如果不存在显然这是无穷大)那么我们可以搞出这么一个转移方程f[i] = min(f[j – 1]+ cnt[j][i] * (i -j + 1) + k)。我们相[……]

Read more