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

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

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

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

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

Read more

POJ 1470 Closest Common Ancestors tarjan LCA

题目没写多case,然而却是多case题,坑死了…

POJ 1330 Nearest Common Ancestors 倍增LCA

POJ 1330 Nearest Common Ancestors ST表LCA

POJ 1637 Sightseeing tour 混合图欧拉回路 网络流

先考虑联通性,不连通则无解。

再给所有双向边钦点一个方向,和单向边一样记录入度出度。

然后我们考虑,对于一个点,把一条双向边的方向改变,入度-出度的奇偶性是不变的,这样子我们看一下,所有点的入度-出度,如果为奇数,则无解。

然后我们对于每个点,如果其出度大于入度,则从s到i连一条流[……]

Read more

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

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

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

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

Read more

BZOJ 2199 && luguoP3007 [USACO11JAN]大陆议会The Continental Cowngress 2-sat

对板子有了更深刻的理解,只要2-sat存在,那么dfs函数求出的一个方案一定是一个合法解的子集。

BZOJ 1823 1823: [JSOI2010]满汉全席 2-sat

对这套2-sat板子又有了更深刻的理解。现在感觉kuangbin这套板子真的很妙,应该可以处理所有的2-sat问题。

POJ 3683 Priest John’s Busiest Day 2-sat

就是两个时间段必须选一个,依旧用的kuangbin的那套理论。现在我觉得这套理论可能只支持两个只能选一个情况。还在研究。

hdu 1814 Peaceful Commission 2-sat

观摩了下kuangbin大佬的板子。太简洁巧妙了!但是感觉似乎这个板子对于两个东西至少选一个不是通过建边保证,而是用了其他的方式,感觉也不不太通用,自己在多了解了解