采取逆向思维。问题就变成我们采取不断合并的策略,使得总代价最大。于是变成了经典的哈夫曼树题。每次从剩下的元素中挑选两个最大的进行合并,直至剩下一个元素。此题得解。
通过一些观察可得:节点 u 到节点 v 的最短路肯定为以下两种情况之一:
1、不经过额外的 m 条边直接从 u 到 v。
2、从 u 先走到某个为额外边端点的 x,再从 x 走到某个同样为额外边端点的 y,最后从y 走到 v。
预处理所有额外边的端点间两两最短路,询问时暴力枚举 x、y 更新答案即可。
时间复杂度: O(M 3 + N + Q ×M 3 。
进一步观察可得,以上第二种路径可进一步化简为:从 u 先走到第一个为特殊边端点的x,再从 x 走到最后一个为特殊边端点的 y,最后从 y 走到 v,这样的 x 和 y 都是与 u 和 v 相邻的。
故我们只需要预处理出与 u 相邻的两个 x 和与 v 相邻的两个 y,就可以计算出答案了。时间复杂度: O(M 3 + N + Q) 。
用 d[i][j]表示从(i, j)位置向下连续有多少个 X,用 dr[i][j]表示从(i, j)位置向右下连续有多少个 X,用 dl[i][j]表示从(i, j)位置向左下连续有多少个 X,设 f[i][j] = min(d[i][j], dr[i][j]),v[i][j] = min(d[i][j], dl[i][j]),枚举蝴蝶的左上角(i, j),问题就变成了找到对应的右上角(i, k),使得 f[i][j] >= k – j + 1 且 v[i][k] >= k – j + 1 且 k 最大。移一下前面的式子,即我们要在区间(j, f[i][j] + j – 1)里找到最大的 k,使得满足 j >= k - v[i][k] + 1。我们把 k 按照 k - v[i][k] +1 排序,随着 j 从左到右枚举,一点一点把 k 加进考虑的范畴,于是问题变成了在一段区间里找一个最大的 k,随便怎么弄都可以啦!std选择了线段树,也可以使用并查集路径压缩大法。复杂度 O(nmlogm)
考虑到图是 DAG 形态,那么删掉一个点 N 以后会发生什么呢?考虑拓扑序,一定有一条边从 N 的左边连接到 N 的右边。我们可以枚举所有的边(x,y),用 dist(S, x) + v(x, y) + dist(y, T)更新拓扑序中(x, y)区间的最小值。查询的时候线段树里找一找就可以啦!
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305
全部评论
(0) 回帖