P11321 题解

0 前言

一道相当奇怪的题目，

思路和做法参考了题解区第一篇题解，十分感谢。

1 题意

给出一个 $n$ 点 $m$ 边的无向图，不一定连通，里面有 $k$ 个关键点，你需要不重复的选择 $4$ 个关键点 $v_1,v_2,v_3,v_4$，使得$dis(v_1,v_2)+dis(v_3,v_4)$ 最小，若 $a,b$ 不连通则 $dis(a,b)=+\infty$。

2 思路

首先看到这题的思路一定是想办法对关键点跑全源最短路，求出关键点两两之间 $dis$ 然后进一步处理。但是很显然，在 $n\le 10^5,m\le 3\times 10^6$ 的数据规模下是不现实的。

然后一个比较聪明的优化办法是，考虑关键点 $v_1,v_2$ 在什么情况下可能对答案有贡献，显然当且仅当他们是“相邻”的时候。

所谓“相邻”，就是令 $b_i$ 表示距离点 $i$ 最近的关键点编号，如果存在至少一条边 $(u,v)$ 使得 $b_u=b_v$，那么我们认为 $b_u$ 和 $b_v$ 是相邻的。

这个东西感性理解一下。笔者暂时不会证明

然后事实上就是枚举这样边的数量，然后令 $dis_u$ 表示 $u$ 到最近的关键点的距离，那么通过计算 $dis_u+dis_v+val_{u,v}$ 来等待更新后面的答案，可以先把他们都存起来。

然而重点是后面的策略。

起初的思路是按照以下两种方案选择，然后取其最优：

• 选一条“最短路”，再往下选一条最优的和“最短路”无交的路；
• 从最短路的两个端点分别选一条从此点延伸出去的最短路。

然后这样能够获得 $30pts$。

这样的策略乍一看好像是对的，但是仔细一想就可以发现一种简单的反例：有很多都是最短的路，但是你目前的“最短路”并不最优（也就是和很多其他路径有交）。

然而改动十分简单：再多枚举一条“次短路”和其他所有路径更新答案，就可以解决。

3 实现

具体实现上有一个经典问题：怎么求出每个店最近的关键点？

实现上非常的简单：建一个虚拟原点，连向所有的关键点一条边权为0的边，对这个虚拟原点跑最短路，然后至于处理 $b_i$ 稍微改一下最短路就好。

丑陋的部分代码：

int n,m,k;
struct nd{
    int to,val;
    friend bool operator<(nd x,nd y){
        return x.val>y.val;
    }
};
struct edge{
    int st,to,val;
};
std::vector<edge> edgeset;
std::vector<nd> g[N];
int a[N],dis[N],b[N];
bool vis[N];
std::priority_queue<nd> que;
void dij(){
    for(int i=1;i<=k;++i)b[a[i]]=a[i];
    for(int i=1;i<=n;++i)dis[i]=LONG_LONG_MAX;
    dis[0]=0;
    que.push({0,0});
    while(!que.empty()){
        auto tmp=que.top();
        que.pop();
        if(vis[tmp.to])continue;
        vis[tmp.to]=1;
        for(auto &i:g[tmp.to]){
            if(dis[i.to]>dis[tmp.to]+i.val){
                dis[i.to]=dis[tmp.to]+i.val;
                que.push({i.to,dis[i.to]});
                if(tmp.to==0)continue;
                b[i.to]=b[tmp.to];
            }
        }
    }
}
struct node{
    int st,to,dis;
    friend bool operator<(node x,node y){
        return x.dis<y.dis;
    }
};
std::priority_queue<node> minque[N];
std::vector<node> tmp1;
int minans[N];
void solve(){
    dij();
    node minn={inf,inf,inf};
    //枚举所有的两端bi不相同的边
    for(auto &i:edgeset){
        if(b[i.st]==b[i.to])continue;
        minque[i.st].push({b[i.st],b[i.to],dis[i.st]+dis[i.to]+i.val});
        minque[i.to].push({b[i.to],b[i.st],dis[i.st]+dis[i.to]+i.val});
        tmp1.push_back({b[i.st],b[i.to],dis[i.st]+dis[i.to]+i.val});
        if(dis[i.st]+dis[i.to]+i.val<minn.dis){
            minn={b[i.st],b[i.to],dis[i.st]+dis[i.to]+i.val};
        }
    }
    //尝试选“最短路”和“次短路”和其他路径组合
    int cimin=inf;
    sort(tmp1.begin(),tmp1.end());
    for(int i=0;i<2;++i){
        for(int j=i+1;j<tmp1.size();++j){
           if(tmp1[i].st!=tmp1[j].st&&tmp1[i].st!=tmp1[j].to&&tmp1[i].to!=tmp1[j].st&&tmp1[i].to!=tmp1[j].to){
                cimin=std::min(tmp1[i].dis+tmp1[j].dis,cimin);
            }
        }
    }
    //尝试选最短路的两个端点的路径
    int minx=inf,minc=inf;
    while(!minque[minn.st].empty()){
        auto tmp=minque[minn.st].top();minque[minn.st].pop();
        if(tmp.st==minn.st&&tmp.to!=minn.to){minx=tmp.dis;break;}
    }while(!minque[minn.to].empty()){
        auto tmp=minque[minn.to].top();minque[minn.to].pop();
        if(tmp.st==minn.to&&tmp.to!=minn.st){minc=tmp.dis;break;}
    }
    //答案
    printf("%lld",std::min(inf,cimin));
}
signed main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        edgeset.push_back({u,v,w});
    }
    for(int i=1;i<=k;++i){
        a[i]=read();
        g[0].push_back({a[i],0});
    }
    solve();
    return 0;
}

以上代码可以通过本题的全部测试数据。

4 但是？

这题就这样结束了吗？

如果这题仅限于此那么并算不上奇怪。

以上思路大体是按照题解区第一篇写的，也确实能够通过本题的全部测试数据。

但是我们考虑一个菊花图：

4 3 4 
1 2 1
1 3 1
1 4 1
1 2 3 4

把这个东西放到程序里面跑一下，发现竟然输出了 $+\infty$ ！

所以，回到开头：

然后一个比较聪明的优化办法是，考虑关键点 $v_1,v_2$ 在什么情况下可能对答案有贡献，显然当且仅当他们是“相邻”的时候……吗？

很显然，这个样例的一个最优方案是 1 2,3 4，而其中3 4 显然不“相邻”。

所以想要解决这个问题，需要找出类似这样的所谓的"根节点"，然后跑一遍最短路，再尝试最优方案拼接，可能会解决这个问题。

但是这里的实现笔者也没有写，因为可能很难写。

5 后记

真的很奇怪。

还是多听听歌。