P2176 [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S

· · 题解

P2176 [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S

题目翻译：

给定一个无向连通图，共有 n 个节点，和 m 条边。求若可以使任意一条边的边权翻倍，那怎样翻倍才能使其最短路长度的增值最多，即让一条路边权翻倍使得翻倍后的最短路长度与翻倍前最短路长度的差最大，并输出这个差。

思路：

本题由于是求最短路，且无负边权，考虑用 dijkstra 但题目中，节点数 n 较少，而边数 m 较多，为稠密图，所以这里用复杂度为 O(n^2) 的普通 dijkstra 反而比复杂度为 O((n+m)log n) 的堆优化后的 dijkstra 好。我们只需要暴力枚举每个边，使其翻倍，求出最大值即可。

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct edge{
    int v,w;
};
vector<edge>e[N];
int dis[N];
bool vis[N];
int n,m;
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    for(int i=1;i<=n;i++){
        int u=0,mi=0x3f3f3f3f;
        for(int j=1;j<=n;j++){
            if(dis[j]<mi && !vis[j]){
                mi=dis[j];
                u=j;
            }
        }
        vis[u]=1;
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dijkstra();
    int mx=dis[n],ans=0;
    //cout<<mx<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<e[i].size();j++){
            int now=e[i][j].w;
            e[i][j].w*=2;
            dijkstra();
            //cout<<endl;
            //cout<<dis[n]<<endl;
            ans=max(ans,dis[n]-mx);
            e[i][j].w=now;
        }
    }
    printf("%d",ans);
}

dijkstra 讲解