[WC2010]重建計劃

• problem
• solution
• code

problem

洛谷指路

solution

一看那個道路平均價值的式子：$\text{AvgValue}=\frac{{\sum }_{e\in S}v(e)}{|S|}$ 就是 0/1分數規劃 的樣子。

所以考慮二分最終的答案 $mid$，考慮是否有一條路徑的平均價值 $\ge mid$，但這個形式仍然跟具體路徑的條數有關。

不妨將每條邊的邊權都減去 $mid$，問題轉化為 $\text{check}$ 是否有一條長度在 $[L,U]$ 內且邊權和 $\ge 0$ 的路徑。

路徑問題就套路的點分治，處理經過分治中心的路徑情況。

一條過分治中心的路徑是由兩個不同子樹內的路徑拼接起來的。

所以單獨依次考慮分治中心的每個子樹。

首先得 dfs 一遍子樹，求出子樹內每個點的距離分治中心的路徑權值，即 dis[i]。

考慮現在枚舉的子樹和之前已經處理過的子樹拼接出來的路徑。

要求兩個路徑的長度之和在 $[L,U]$ 的范圍內，而且我們并不關心具體是哪兩個點，只關心這兩個點的深度。并且整個操作都是為了找一條 $\ge 0$ 的路徑。

所以直接枚舉長度（深度），并且長度相同的點取路徑權值更大的點。

f[i] ：前面處理過的子樹中點深度為 $i$ 的，到分治中心路徑權值的最大值。

g[i] ：當前枚舉的子樹中點深度為 $i$ 的，到分治中心路徑權值的最大值。

那么每次處理下一個子樹前，還要進行二者的合并，即 f[i]=max(f[i],g[i])。

這個信息的維護通過 dfs 每個子樹可以獲得，即 g[dep[u]]=max(g[dep[u]],dis[u])。

然后枚舉兩個深度求：${\max }_{L\le i+j\le U}\{f[i]+g[j]\}$。

轉換一下當現在枚舉的子樹選擇的深度 $j$ 固定時，有 $L?j\le i\le U?j$。

發現隨著 $j$ 的增大，$i$ 枚舉的范圍也在增大。

所以可以單調隊列維護 $i$ 優化成線性。

如果只是這樣，跑出來可能會發現 TLE。

考慮這樣一種情況：$L=1,U=\frac{n}{2}$，數據構造了一條點數為 $\frac{n}{2}$ 的鏈，然后在鏈的一端構造了一個點數為 $\frac{n}{2}$ 的菊花。

分治中心顯然是會選在菊花和鏈的交界處。

然后如果第一棵子樹選擇訪問了那一條鏈，更新了長度在 $1$ 到 $\frac{n}{2}$ 的最優答案。

再去訪問菊花中的每一個點的時，則每一次都需要枚舉 $1～\frac{n}{2}$，對單調隊列進行初始化，結果導致光這一層分治的復雜度就變成了 $O(\frac{n}{2})$。

事實上，這個問題源于每一次單調隊列初始化的復雜度其實是 $O(min(U?1,MaxLen))$ 的，其中$MaxLen$ 為之前訪問的所有子樹中路徑的最長長度（最大深度）。

如果我們在本身 $U$ 就比較大的情況下，選擇先操作較長的子樹，將 $MaxLen$ 變到很大，然后再不斷地進行后續單調隊列的操作，那復雜度肯定就炸了。

解決方法就是啟發式合并，按照子樹的最長長度（最大深度）排序，從小到大處理子樹。

即 sort(s+1,s+cnt+1,[](int x, int y){ return h[x] < h[y]; })。

這樣就有正確的時間復雜度 $O(n{\log }^{2}n)$。

code

#include <bits/stdc++.h> using namespace std; #define eps 1e-4 #define maxn 100005 #define inf 0x7f7f7f7f double ans; int n, L, U, N, Max, root, cnt = 1; double f[maxn], g[maxn], dis[maxn]; int h[maxn], s[maxn], q[maxn], dep[maxn], len[maxn], siz[maxn], head[maxn]; bool vis[maxn]; struct node { int to, nxt, d; }E[maxn << 1];void dfs( int u, int fa ) {siz[u] = 1; int maxson = 0;for( int i = head[u];i;i = E[i].nxt ) {int v = E[i].to;if( vis[v] or v == fa ) continue;else dfs( v, u );siz[u] += siz[v];maxson = max( maxson, siz[v] );}maxson = max( maxson, N - siz[u] );if( maxson < Max ) Max = maxson, root = u; }void dfs1( int u, int fa ) {dep[u] = dep[fa] + 1, h[u] = 1;for( int i = head[u];i;i = E[i].nxt ) {int v = E[i].to, w = E[i].d;if( vis[v] or v == fa ) continue;else len[v] = w, dfs1( v, u ), h[u] = max( h[u], h[v] + 1 );} }void dfs2( int u, int fa, double mid ) {dis[u] = dis[fa] + len[u] - mid, g[dep[u]] = max( g[dep[u]], dis[u] );for( int i = head[u];i;i = E[i].nxt ) {int v = E[i].to;if( vis[v] or v == fa ) continue;else dfs2( v, u, mid );} }bool check( double mid ) {double ret = -inf;for( int i = 1;i <= cnt;i ++ ) {for( int j = 1;j <= h[s[i]];j ++ ) g[j] = -inf;dfs2( s[i], root, mid );int head = 1, tail = 0;for( int j = 0;j <= h[s[i]];j ++ ) {while( head <= tail and q[head] > U - j ) head ++;if( L - j <= h[s[i]] ) {while( head <= tail and f[q[tail]] < f[L - j] ) tail --;q[++ tail] = L - j;}if( head <= tail ) ret = max( ret, f[q[head]] + g[j] );}for( int j = 1;j <= h[s[i]];j ++ ) f[j] = max( f[j], g[j] );}return ret > 0; }void solve( int u ) {vis[u] = 1, dis[u] = 0, dep[0] = -1;dfs1( u, 0 );cnt = 0;for( int i = head[u];i;i = E[i].nxt )if( ! vis[E[i].to] ) s[++ cnt] = E[i].to;if( ! cnt ) return;sort( s + 1, s + cnt + 1, []( int x, int y ) { return h[x] < h[y]; });double l = ans, r = 1e6;while( r - l > eps ) {double mid = ( l + r ) / 2;for( int i = 1;i <= h[s[cnt]];i ++ ) f[i] = -inf; f[0] = 0;if( check( mid ) ) ans = max( ans, mid ), l = mid;else r = mid;}for( int i = head[u];i;i = E[i].nxt ) {int v = E[i].to;if( vis[v] ) continue;N = siz[v], Max = inf;dfs( v, u );solve( root );} }int main() {scanf( "%d %d %d", &n, &L, &U );for( int i = 1, u, v, w;i < n;i ++ ) {scanf( "%d %d %d", &u, &v, &w );E[cnt] = { v, head[u], w }, head[u] = cnt ++;E[cnt] = { u, head[v], w }, head[v] = cnt ++;}Max = inf, N = n;dfs( 1, 0 );solve( root );printf( "%.3f\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的[luogu 4292][bzoj 1758][WC2010] 重建计划（点分治 + dp + 单调队列优化 + 启发式合并）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。