【cf543X】Codeforces Round #302 (Div. 1)

2015年5月8日1,3491

本场血崩

A. Writing Code

显然的n^3 dp,滚动数组

B. Destroying Roads

n个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。

\(1\leq n\leq 500,1\leq m\leq n(n-1)/2\)

题解

其实就是问,至少需要多少条边,才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。

如果这两条路径不相交,那么答案为dis(s1,t1)+dis(s2,t2)。

如果相交部分为(p1,p2),答案为p1,p2的最短路,加上p1,p2到其它4个点的最短路。

预处理任意点对距离,枚举两条路径重叠部分。

D. Road Improvement

两遍树形dp

 

  • 梁爽2015年5月9日 下午11:24 回复

    请问D题的两个dp是什么意思啊…

    #1