『FLA - I』庭中有奇树

ScaredQiu · 2024-02-25 22:40:14 · 题解

二分答案

小 Y 是 Ycyofmine，小 G 是不知名人士。

Subtask #1

预处理每个节点到 S 和 T 的距离，枚举点对 (u,v)，如果枚举到的点对没有连边则计算从 S 到达 T 且中途从 u 传送到 v 的路径代价。

找到第 m+1 小的路径代价，比较其与直接走树边和花费 10^9 代价传送的代价，三种情况中的最小值即为答案。

时间复杂度 O(n^2 \log n)，容易优化到 O(n^2)。

Subtask #2

注意到 m=0，此时可以直接从 S 传送到 T，比较 k 和走树边的代价大小，较小值即为答案。

时间复杂度 O(n)。

该做法可以通过 Subtask #2 和 Subtask #4 并获得 25 分。

Subtask #3

考虑贪心，类似最小函数值，使用堆维护全局最小路径，扩展到全局第 m+1 小路径。

比较第 m+1 小路径、走树边和在封锁路径上传送的代价，三种情况中的最小值即为答案。

时间复杂度 O(m \log n)。

该做法可以通过前三个 Subtask 并获得 30 分。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=1'000'000'000ll;
struct Path{
    int i;long long w;
    Path(int x,long long y):i(x),w(y){}
    Path(){}
    bool operator<(const Path &x)const{
        return this->w>x.w;
    }
}d[100'005],p[100'005];
struct Edge{int w,to;Edge(int x,int y):w(x),to(y){}};
unordered_map<int,bool> on[100'005];
int n,m,k,S,T,pos[100'005];
vector<Edge> v[100'005];
priority_queue<Path> q;
void dfs(int x,int las,Path *u){
    for(auto i:v[x]) if(i.to!=las) u[i.to].w=u[x].w+i.w,dfs(i.to,x,u);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>k>>S>>T;
    for(int i=1;i<=n-1;i++){
        static int x,y,w;
        cin>>x>>y>>w;
        v[x].push_back(Edge(w,y));
        v[y].push_back(Edge(w,x));
        on[x][y]=1,on[y][x]=1;
    }
    for(int i=1;i<=n;i++) d[i].i=i,p[i].i=i;
    dfs(S,0,d),dfs(T,0,p);
    sort(p+1,p+n+1,[](auto x,auto y){return x.w<y.w;});
    fill(pos+1,pos+n+1,1);
    for(int i=1;i<=n;i++){
        while(pos[i]<=n&&on[i][p[pos[i]].i]) ++pos[i];
        if(pos[i]<=n) q.push(Path(i,d[i].w+p[pos[i]].w+k)),++pos[i];
    }
    for(int i=1;i<=m&&!q.empty();i++){
        auto now=q.top();q.pop();
        while(pos[now.i]<=n&&on[now.i][p[pos[now.i]].i]) ++pos[now.i];
        if(pos[now.i]<=n) q.push(Path(now.i,d[now.i].w+p[pos[now.i]].w+k)),++pos[now.i];
    }
    long long ans=inf;
    if(!q.empty()) ans=min(ans,q.top().w);
    ans=min(ans,d[T].w);
    cout<<ans<<'\n';
    return 0;
}

Subtask #4

注意到 k=10^9，封锁不会对传送造成影响，比较 10^9 和走树边的代价大小，较小值即为答案。

时间复杂度 O(n)。

Subtask #5

注意到 k=0，传送没有代价，考虑二分使用传送操作到达节点 T 的路径代价。对于给定的值 x 计算能凑出多少条长度不大于它的路径，若路径数量大于 m，则花费 x 代价必定能从 S 到 T，因为只有前 m 小的路径会被封锁。

具体地，处理出节点到 S 和 T 的距离之后将每个节点到 T 的距离从小到大排序，检查给定的值 x 时枚举每个节点，令节点 u 到 S 的距离为 dis_{u,S}，二分得到满足 dis_{u,S}+dis_{v,T} \leq x 的节点 v 的数量，枚举与 u 连边的节点排除不可传送的情况。

时间复杂度 O(n \log n \log V)，其中 V 为二分上界。

Subtask #6

扩展 Subtask #5 的做法，二分出不包含 k 的第 m+1 小路径代价后，将代价加上 k 并与直接走树边、花费 10^9 代价传送比较，取最小值即可。

时间复杂度 O(n \log n \log V)，这里给出验题人 shinzanmono 的代码。

#include<iostream>
#include<algorithm>
using ll=long long;
const int sz=1e5+10;
struct edge{
    int nxt,to,w;
}graph[sz<<1];
int head[sz],hpp;
void addEdge(int from,int to,int w){
    graph[++hpp]=edge{head[from],to,w};
    head[from]=hpp;
}
ll diss[sz],dist[sz];
void dfs(int u,int fau,ll *dis){
    for(int p=head[u];p;p=graph[p].nxt){
        int v=graph[p].to;
        if(v==fau)continue;
        dis[v]=dis[u]+graph[p].w;
        dfs(v,u,dis);
    }
}
int n,m,k,s,t;
std::basic_string<ll>td;
ll rank(ll dis){
    ll tot=0;
    for(int u=1;u<=n;u++){
        if(diss[u]+dist[u]<=dis)tot--;
        for(int p=head[u];p;p=graph[p].nxt){
            int v=graph[p].to;
            if(dist[v]+diss[u]<=dis)tot--;
        }
        tot+=std::upper_bound(td.begin(),td.end(),dis-diss[u])-td.begin();
    }
    return tot;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>n>>m>>k>>s>>t;
    for(int i=1,u,v,w;i<n;i++)
        std::cin>>u>>v>>w,addEdge(u,v,w),addEdge(v,u,w);
    dfs(s,0,diss),dfs(t,0,dist);
    for(int i=1;i<=n;i++)td+=dist[i];
    std::sort(td.begin(),td.end());
    ll l=0,r=1e18;
    while(l<r){
        ll mid=l+r>>1;
        if(rank(mid)>=m+1)r=mid;
        else l=mid+1;
    }
    std::cout<<std::min({diss[t],l+k,1000000000ll})<<"\n";
    return 0;
}

可以双指针将检查的时间复杂度优化到 O(n)，总体时间复杂度 O(n \log V)。

这里列举一些实现中的细节。

写 30 分做法时，堆可能被删空。
路径数量会爆 int，不开 long long 只能获得 25 分。
二分下界是 0，设为 1 只能获得 50 分。
走树边和花费 10^9 代价传送的情况都可能比找到没被封锁的点对后传送更优。
没有必要排除原地传送的情况，原地传送能计入路径数时走树边必定不劣。
~~我的代码跑构造数据访问了 99999 次空堆但结果还是对的。~~

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=1'000'000'000ll;
struct Edge{int w,to;Edge(int x,int y):w(x),to(y){}};
struct Path{int i;long long w;}d[100'005],p[100'005];
vector<Edge> v[100'005];
long long dis[100'005];
int n,m,k,S,T;
void dfs(int x,int las,Path *u){
    for(auto i:v[x]) if(i.to!=las) u[i.to].w=u[x].w+i.w,dfs(i.to,x,u);
}
bool fail(long long x){
    long long sum=0ll;
    int pos=n;
    for(int i=1;i<=n;i++){
        while(pos&&d[i].w+p[pos].w>x) --pos;
        sum+=pos;
        for(auto j:v[d[i].i]) if(d[i].w+dis[j.to]<=x) --sum;
        if(d[i].w+dis[d[i].i]<=x) --sum;
    }
    return sum<=m;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>k>>S>>T;
    for(int i=1;i<=n-1;i++){
        static int x,y,w;
        cin>>x>>y>>w;
        v[x].push_back(Edge(w,y));
        v[y].push_back(Edge(w,x));
    }
    for(int i=1;i<=n;i++) d[i].i=i,p[i].i=i;
    dfs(S,0,d),dfs(T,0,p);
    for(int i=1;i<=n;i++) dis[i]=p[i].w;
    sort(d+1,d+n+1,[](auto x,auto y){return x.w<y.w;});
    sort(p+1,p+n+1,[](auto x,auto y){return x.w<y.w;});
    long long l=0ll,r=inf,ans=inf;
    while(l<=r){
        long long mid=(l+r)/2;
        if(fail(mid)) l=mid+1;
        else ans=mid,r=mid-1;
    }
    ans=min(ans+k,min(inf,dis[S]));
    cout<<ans<<'\n';
    return 0;
}