SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1001][BEIJING2006]狼抓兔子(最小割 + DIJKSTRA)

这道题很裸的最小割,只是数据规模大,目测会T(WJS大爷说在BZ上能过,真是跪烂了),其实最小割可以转成最短路的做法。一种做法是转成对偶图然后求最短路,当然我不会,就只好去墙角画圈圈了。不过有一天没事乱翻LRJ的白书突然就翻到了这道题(我真的只是乱翻),然后就观摩了一下题解。转什么对偶图啊。。对于这道题,由于这个图样子比较特殊,可以知道割线必然是一条从图的左边界或下边界的边出发,经过若干条边到达右边界或上边界的边,需要的狼的数量就是经过的所有边的权值和。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1003][ZJOI2006]物流运输(DP + DIJKSTRA)

好吧这就是一道大水题,很显然的DP思路。DP状态转移方程就是(dpi = text{min}(f{1,i}, dpj + k + f{j+1,i}) (1 leq j < i)),其中(f{i,j})表示从i时刻到j时刻(包括i和j)走同一条路所需的总成本。而由于n和m都很小,这个直接暴力标记不能走的点然后做一次DIJKSTRA就可以了,同时把已经计算过的(f{i,j})存下来,以便下次使用。这样的话总体的时间复杂度大概就是(原谅我不会算,随便乱估计的)(text{O}(n^2 log_2 m))。     Read more