「CF543X」Codeforces Round #302 (Div. 1)

2015年5月8日3,1191

本场血崩

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

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
梁爽 Recent comment authors
  Subscribe  
提醒
梁爽
梁爽

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