题解 P2185 【公路通行税】

· · 题解

我们机房的一位大佬曾经说过：

拿到一道题，要先把它简化了再做。

正文：

题目的大意：

在一个无向连通图中，求任意两点的最短路的最大值，答案乘上100后输出。

注意：有多组数据，当 n 和 m 都为 0 时结束程序

思路：

1、安息的 SPFA算法：

我自己就让我的程序TLE了，我还要交到评测姬上吗？

对于每一个图，遍历每个点，以这个点为起点做一次SPFA，得到以这个点为起点的最短路的最大值。最后把这些最大值取max，乘上100输出。

最优的时间复杂度：O(T*(n+m))

最坏的时间复杂度：O(T*nm)

2、Dijkstra算法：60分

因为在这个无向图中，每条边的边权都为1，所以我们可以用Dijkstra。

对于每一个图，遍历每个点，以这个点为起点做一次Dijkstra，得到以这个点为起点的最短路的最大值。最后把这些最大值取max，乘上100输出。（直接复制粘贴上面的）

时间复杂度：O(T*nmlog_2 m)

3、貌似很暴力的bfs：100分

按照SPFA的思路，遍历每个点，以这个点为起点进行bfs。

那么，为什么bfs是正确的：

因为每条边的边权都是1，所以我们不用像求最短路一样要做松弛操作。这也意味着，我们在bfs的时候，每个点被第一次搜到时与起点的距离就是最短的，所以我们不用像Dijkstra一样要用个优先队列一样找到最小的边并进行松弛操作。

又\because 这是一个图。

$\therefore$ 在遍历的时候，我们可以记录这个起点到每一个点的距离，记录的时候就可以顺便取max 时间复杂度：$O(T*nm)

到此，我们直接写个图的bfs遍历不就行了？

我的100分代码：

#include<stdio.h>
#include<cstring>
#include<queue>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
int n,m;
struct edge{
    int to,nxt;
}e[50005];//使用链式前向星存图 
int hed[50005],cnt;//注意每组数据开始前要把hed和cnt数组清零 

inline void add(int u,int v){
    e[++cnt].to = v;
    e[cnt].nxt = hed[u];
    hed[u] = cnt;
}

bool vis[1005];//记得清零 

struct node{
    int tp,dis;//tp:当前点的编号;dis:从起点到这个点的距离 
};

int ans = -1;//最终的答案 
inline void bfs(int s){
    queue<node> q;
    q.push((node){s,0});//初始状态 
    vis[s] = true; 
    while(!q.empty()){
        node fr = q.front();
        q.pop();
        int u = fr.tp,dis = fr.dis;
        ans = max(ans,dis);//在遍历每个点的时候更新答案 
        for(int i = hed[u];i;i = e[i].nxt){
            int v = e[i].to;
            if(vis[v]) continue;
            q.push((node){v,dis+1});
            vis[v] = true;
        }
    }
}
int main(){
    while(true){
        scanf("%d%d",&n,&m);
        if(n==0 && m==0) break;
        ans = -1;//清零 
        memset(hed,0,sizeof(hed));
        cnt = 0;
        int u,v;
        for(register int i = 1;i<=m;++i){
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u);//加双向边 
        }
        for(register int i = 1;i<=n;++i){//以i为起点进行bfs 
            memset(vis,false,sizeof(vis));//每次bfs开始前进行清零 
            bfs(i);
        }
        printf("%d\n",ans*100);
    }
    return 0;
}