题解 JOI 公園 (JOI Park)

cjh20090318 · 2024-01-27 16:00:42 · 题解

题目链接。

题意

城市中有 N 个公园，编号 1\sim N，有 M 条双向道路将 N 个公园连通，第 i 条道路连接公园 x_i,y_i，长度为 d_i，使得任何两个公园之间都能直接或间接到达。

现在计划对公园的道路进行改造：

• 你可以选择一个自然数 X，将第 1 个公园到其他公园最短路小于等于 X 的都修建一条地下通道，费用为 X\times C，C 是给定的一个整数。
• 接下来，将通过地下通道连接的公园之间的道路删除，即 x,y 都和 1 有地下通道，删除 x,y 的道路。
• 对于剩下的道路，长度为 k 的道路，维护的费用是 k。

初始时，没有地下通道，你需要输出改造的最小总费用。

分析

首先用优先队列优化的 Dijkstra 算法求出第 1 个公园到其他所有公园的最短路。

直接枚举 X 一定是不可行的，观察到 X 一定是 1 到其中一个点的最短路值，否则会产生多余的花费，因此枚举时间复杂度是 O(N)。

对于每一个 X 单独删边的时间复杂度为 O(NM)，但是随着 X 的增大，能修地下通道的点就越多，边就删除的越多，剩下维护的边权和就越小。

所以提前对可行的 X 进行排序，每次新加入一个点就将其原来所有连了地下通道的边全部删掉，每条边至多访问两次，时间复杂度 O(N+M)。

总体时间复杂度 O(M \log N)，瓶颈在于单源最短路和对可行 X 值的排序。

代码

//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<utility>
#include<vector>
#define MAXN 100005
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
int n,m,c;
vector<PII> G[MAXN];
LL dis[MAXN];
bool vis[MAXN];
void dj(const int S){//Dijkstra 算法求单源最短路。
    memset(dis,0x3f,sizeof(LL)*(n+1));
    priority_queue<PLI,vector<PLI>,greater<PLI> > Q;
    Q.emplace(dis[S]=0,S);
    for(int u;!Q.empty();){
        u=Q.top().second;Q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(const PII&V:G[u])if(dis[u]+V.second<dis[V.first])
            Q.emplace(dis[V.first]=dis[u]+V.second,V.first);
    }
}
int p[MAXN];
bool cmp(const int x,const int y){return dis[x]<dis[y];}//按照最短路大小排序。
bool S[MAXN];
int main(){
    scanf("%d%d%d",&n,&m,&c);
    LL ds=0;//边权和。
    for(int i=1,u,v,w;i<=m;i++)
        scanf("%d%d%d",&u,&v,&w),G[u].emplace_back(v,w),G[v].emplace_back(u,w),ds+=w;
    dj(1);
    for(int i=1;i<n;i++) p[i]=i+1;
    sort(p+1,p+n,cmp);
    LL ans=ds;//X=0，不需要建立任何地下通道，答案即为边权和。
    S[1]=1;
    for(int j=1;j<n;++j){
        LL s=dis[p[j]];
        for(const PII&V:G[p[j]])if(S[V.first]) ds-=V.second;//删去原来有地下通道的点的连边。
        S[p[j]]=1;//将当前点加入地下通道联通的点集合。
        ans=min(ans,ds+s*c);
    }
    printf("%lld\n",ans);
    return 0;
}