CF566C Logistical Questions

分析

首先,设 \(d(i,j)\) 表示当前定义下 i,j 的距离,然后可以发现,当 j 固定,i 在一条路径上移动时,\(d\) 是下凸函数,就是说只会有一个最优解。。

然后考虑 \(f(i)\),表示以 i 为重心时的答案。

有:\(f(i)=\sum_{j\neq i}f(i,j)\)。

然后由于下凸函数相加后也为下凸函数,所以 \(f(i)\) 也为下凸函数。

所以全树只有一个最优位置(不一定为节点),且从此扩散出去的点的答案会变大。

于是考虑链的情况,二分就完事了。

然后放到树上,就可以点分治,每次在根的相邻节点中选出会使答案变小的方向,继续点分。

然后显然我们不能每次都暴力计算 \(f\),我们可以利用导数来快速计算。

注意

codeforces 好像不可以用 long double。。

然后最大值要算好设。。。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
template <class I>
inline void read(I &x){
    int f=1;
    char c;
    for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c&15),c=getchar());
    x*=f;
}
int n,w[N];
int head[N],nxt[2*N],ver[2*N],edge[2*N],tot=1;
inline void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
double res=0;
int rt=0,d[N],sz;
bool v[N];
void getsz(int x,int f){
    d[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(v[y]||y==f) continue;
        getsz(y,x);
        d[x]+=d[y];
    }
}
void getrt(int x,int f){
    d[x]=1;
    int mx=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(v[y]||y==f) continue;
        getrt(y,x);
        d[x]+=d[y];
        if(d[y]>mx) mx=d[y];
    }
    mx=max(mx,sz-d[x]);
    if(mx<=sz/2) rt=x;
}
double ds[N];
void calc(int o,int x,int fa,int dis){
    res+=(double)pow(dis,1.5)*w[x];
    ds[o]+=1.5*pow(dis,0.5)*w[x];
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue;
        calc(o,y,x,dis+edge[i]);
    }
}
int anss;
double ans=1e20;
void dfs(int x){
    getsz(x,0);
    sz=d[x];
    getrt(x,0);
    if(v[x]) return;
    v[x=rt]=1;
    res=0;
    double sds=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        ds[y]=0;
        calc(y,y,x,edge[i]);
        sds+=ds[y];     
    }
    if(ans>res) ans=res,anss=x;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(sds-2*ds[y]>=0) continue;
        dfs(y);
        return;
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;i++) read(w[i]);
    for(int i=1;i<n;i++){
        int x,y,z;
        read(x),read(y),read(z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1);
    printf("%d %.7f\n",anss,ans);
    return 0;
}
上一篇:vue全家桶(2.4)


下一篇:[转]BEC Vantage