e福州官方网站,云南楚雄地图全图,泰安公司做网站,网页设计页面配色分析[WC2010]重建计划problemsolutioncodeproblem
洛谷指路
solution
一看那个道路平均价值的式子#xff1a;AvgValue∑e∈Sv(e)∣S∣\text{AvgValue}\frac{\sum_{e\in S}v(e)}{|S|}AvgValue∣S∣∑e∈Sv(e) 就是 0/1分数规划 的样子。
所以考虑二分最终的答案 midmidmid…
[WC2010]重建计划problemsolutioncodeproblem
洛谷指路
solution
一看那个道路平均价值的式子AvgValue∑e∈Sv(e)∣S∣\text{AvgValue}\frac{\sum_{e\in S}v(e)}{|S|}AvgValue∣S∣∑e∈Sv(e) 就是 0/1分数规划 的样子。
所以考虑二分最终的答案 midmidmid考虑是否有一条路径的平均价值 ≥mid\ge mid≥mid但这个形式仍然跟具体路径的条数有关。
不妨将每条边的边权都减去 midmidmid问题转化为 check\text{check}check 是否有一条长度在 [L,U][L,U][L,U] 内且边权和 ≥0\ge 0≥0 的路径。
路径问题就套路的点分治处理经过分治中心的路径情况。
一条过分治中心的路径是由两个不同子树内的路径拼接起来的。
所以单独依次考虑分治中心的每个子树。
首先得 dfs 一遍子树求出子树内每个点的距离分治中心的路径权值即 dis[i]。
考虑现在枚举的子树和之前已经处理过的子树拼接出来的路径。
要求两个路径的长度之和在 [L,U][L,U][L,U] 的范围内而且我们并不关心具体是哪两个点只关心这两个点的深度。并且整个操作都是为了找一条 ≥0\ge 0≥0 的路径。
所以直接枚举长度深度并且长度相同的点取路径权值更大的点。
f[i] 前面处理过的子树中点深度为 iii 的到分治中心路径权值的最大值。
g[i] 当前枚举的子树中点深度为 iii 的到分治中心路径权值的最大值。
那么每次处理下一个子树前还要进行二者的合并即 f[i]max(f[i],g[i])。
这个信息的维护通过 dfs 每个子树可以获得即 g[dep[u]]max(g[dep[u]],dis[u])。
然后枚举两个深度求maxL≤ij≤U{f[i]g[j]}\max_{L\le ij\le U}\Big\{f[i]g[j]\Big\}maxL≤ij≤U{f[i]g[j]}。
转换一下当现在枚举的子树选择的深度 jjj 固定时有 L−j≤i≤U−jL-j\le i\le U-jL−j≤i≤U−j。
发现随着 jjj 的增大iii 枚举的范围也在增大。
所以可以单调队列维护 iii 优化成线性。
如果只是这样跑出来可能会发现 TLE。
考虑这样一种情况L1,Un2L1,U\frac n2L1,U2n数据构造了一条点数为 n2\frac n22n 的链然后在链的一端构造了一个点数为 n2\frac n22n 的菊花。
分治中心显然是会选在菊花和链的交界处。
然后如果第一棵子树选择访问了那一条链更新了长度在 111 到 n2\frac n22n 的最优答案。
再去访问菊花中的每一个点的时则每一次都需要枚举 1∼n21\sim \frac n21∼2n对单调队列进行初始化结果导致光这一层分治的复杂度就变成了 O(n2)O(\frac n2)O(2n)。
事实上这个问题源于每一次单调队列初始化的复杂度其实是 O(min(U−1,MaxLen))O\Big(min(U−1,MaxLen)\Big)O(min(U−1,MaxLen)) 的其中MaxLenMaxLenMaxLen 为之前访问的所有子树中路径的最长长度最大深度。
如果我们在本身 UUU 就比较大的情况下选择先操作较长的子树将 MaxLenMaxLenMaxLen 变到很大然后再不断地进行后续单调队列的操作那复杂度肯定就炸了。
解决方法就是启发式合并按照子树的最长长度最大深度排序从小到大处理子树。
即 sort(s1,scnt1,[](int x, int y){ return h[x] h[y]; })。
这样就有正确的时间复杂度 O(nlog2n)O(n\log^2n)O(nlog2n)。
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;
}
