题解：P1395 会议

· · 题解

前言

本题其它题解基本都是讲的动态规划做法，我这里提供另一种方法，类似于小奥的经典问题之一。有些地方有一些人，要建一个车站，使所有人到车站距离之和最短，只不过这次不是一条路。不过树上两点之间路径唯一，所以也可以做。

思路

参考小奥做这种题的方法，每一次把会议地点移动至相邻位置，都可以理解为有些人距离加了一，有些人减了一。那么显然如果距离缩短的人数多余距离增加的人数，就划算，反之不划算。而又知每次移动对所有人来说距离一定改变，那就是说如果缩短距离的人数大于总人数一般一半，就朝哪个方向移动一的距离。这样最终我们就可以找到最优的位，然后直接以 O(n) 的时间复杂度求一下距离和就可以了。

做法

那现在的问题就是如何记录每次移动距离缩短的人数。由于是无向图，我们随意选择 1 为根节点。然后简单拓扑排序一下。可以理解为在查询时，将每条路都变为有向路径。

q.push(1);//用队列存储，初始将根节点入栈
while(!q.empty()){
    int nxt=q.front();
    q.pop();
    jz[nxt]=cnt;//进行编号
    cnt++;
    for(auto e:g[nxt]){//这个语句就是遍历所有nxt到达的点
        if(flag[e]==1){//有向路径可以当作每条路只能用一次
            q.push(edge[e][0]+edge[e][1]-nxt);//懒得分类，这样写来找到到达的点
            flag[e]=0;//将这条路径展示删去
        }
    }
}

这样，我们就获得了一颗树。

然后统计每个节点的子树加上它自己共有多少个节点。

void bfs(int s){
    for(auto e:g[s]){
        int to=edge[e][0]+edge[e][1]-s;//也是找到路径所到达的点
        if(jz[s]<jz[to]){//只能向下查询
            bfs(to);
            jds[s]+=jds[to];//将所有子树的节点数相加
        }
    }
}

这里我们初始化每个节点的节点数为 1。

然后就是找到会议位置，还是从根开始往下，查询这个点所有子节点是否值得移动。如果值得，直接移动。如果没有节点值得移动，那这个点自己就是最优点。

void find(int s){
    for(auto e:g[s]){
        int to=edge[e][0]+edge[e][1]-s;
        if(jz[s]>jz[to]) continue;//不能向父节点移动
        if(jds[to]>n/2||(jds[to]==n/2&&s>to)){//如果移动时总距离不变，则选择更小的节点
            find(to);
            return;
        }
    }
    cout<<s<<" ";//这个点就是最优点
    count(s,0);//统计总距离
    cout<<summ;
}

最后的总和计算就很容易了，简单写一写就行了。

void count(int s,int jl){//这个点的编号与距离会议的距离
    vis[s]=1;
    summ+=jl;//总距离计算
    for(auto e:g[s]){
        int to=edge[e][0]+edge[e][1]-s;
        if(vis[to]==0) count(to,jl+1);//每个点只能计算一边
    }
}

最后附上 AC 记录。