缆车

NC234866. 缆车

描述

牛妹：“冬天到了，我们一起去坐缆车吧！”

景区有个景点，入口在编号为 1 的景点的位置，景区内有 - 1 条单向缆车，从编号为 1 的景点可以通过缆车到达任意一个其它的景点。

具体来说所有景点中的道路形成了一个树状结构，树根则是编号为 1 的景点，每条树边都是从父亲指向儿子的单向边。

景区改造开始了，景区现在的管理员牛牛规划出了个结点用于改造，它将指定一个景点作为去向这个景点的中转景点（当然，中转景点本身也可能处在这待改造的个景点中），景区领导打算投资新建一条单向缆车路线使得从景点出发可以到达这个景点，要求从开始分别去向规划出的个景点中的每一个的乘坐缆车数量的和最小，现在需要你帮牛牛计算新建一条缆车之后出从中转点出发最小的乘坐缆车数量和是多少。

输入描述

第一行一个整数代表景点个数。

接下来 - 1 行每行两个整数代表有一条从景点驶向景点的有向缆车路线。

接下来一行两个整数代表规划出的景点个数以及指定的中转景点。

接下来一行

个整数代表规划出的景点编号。

保证输入数据形成一颗树。

景区编号

输出描述

一行一个整数代表最小的从中转点去向选定个景点的乘坐缆车数量的和。

示例1

输入:

输出:

说明:

图形如下：

添加如图所示红线后便使得每个集合内的点通过中转点（这里是点7）后可以到达且游览总和最小。

路径共有四条：

7 -- 1 -- 2 -- 5

7 -- 8

7 -- 1 -- 3 -- 6

7 -- 1 -- 4

所以使用缆车和为：3 + 1 + 3 + 2 = 9。

示例2

输入:

输出:

说明:

从点 6 连向点 2 显然最优，总路径长为 9 。

（此例由网友赛后发现的 hack 数据）

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 155ms, 内存消耗: 25552K, 提交时间: 2022-04-10 21:31:38

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
const int N=200005;
vector<int> nxt[N];
int fa[N],n,m,num[N],k,d[N];
long long sum[N];
void dfs(int x){
    for(auto v:nxt[x]){
        d[v]=d[x]+1;
        dfs(v);
        if(v==k) continue;
        num[x]+=num[v];
        sum[x]+=num[v]+sum[v];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        nxt[u].push_back(v);
        fa[v]=u;
    }
    scanf("%d%d",&m,&k);
    for(int i=1,t;i<=m;i++){
        scanf("%d",&t);
        num[t]+=1;
    }
    dfs(1);
    long long ans=1e18;
    if(num[k]==m){
        ans=sum[k];
        for(int i=1;i<=n;i++)
            ans=min(ans,sum[k]-(d[i]-d[k]-1)*1ll*num[i]);
    }
    else{
        int p=1;
        while(1){
            int q=0;
            for(auto v:nxt[p])
                if(num[p]==num[v]&&v!=k){q=v; break;}
            if(!q) break;
            else p=q;
        }
        for(int i=p;i;i=fa[i])
            ans=min(ans,sum[k]+sum[i]+num[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

上一题

下一题

详情