题解 P2951 【[USACO09OPEN]捉迷藏Hide and Seek】

· · 题解

Update

Content

给定一个有 n 个点、m 条边（每条边边权为 1）的无向图，求从 1 号点到所有点的距离中：

数据范围：2\leqslant n\leqslant 50000,1\leqslant m\leqslant 50000。

Solution

可以发现这里每个边的边权是 1，所以先直接跑跑最短路就行了。

Part 1 Dijkstra+堆优化

下面的代码展示的是堆优化+ \texttt{dijkstra} 的过程，具体思路可以自己画个图加深理解：

void dj() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    q.push(make_pair(0, 1));
    while(!q.empty()) {
        int x = q.top().second;
        q.pop();
        if(vis[x])  continue;
        vis[x] = 1;
        for(int i = h[x]; i; i = e[i].nxt) {
            int v = e[i].to, z = e[i].v;
            if(dis[v] > dis[x] + z) {
                dis[v] = dis[x] + z;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

多说几句写堆优化+ \texttt{dijkstra}要注意的：

  1. 一定要记得将 dis 数组赋初值为 0x3f3f3f！（至于 vis 数组随便，因为它本来的初值都是0）
  2. 不要直接用 memset(dis,0x3f3f3f3f,sizeof(dis))！因为 memset 是按字节赋值的，不然你的程序会炸掉。
  3. 判断是否遍历该点的时候一定要将之前未标记的点标记为 1！不然您的 while 循环会一直循环下去！

Part 2 正解

好了，说了这么多，接下来要讲的是处理最大最短路径的问题。

其实最大最短路径的处理也很简单，首先遍历一遍找出最大最短路径的距离，再遍历看有这个最大最短路径的点的编号是多少，最后统计出这个最大最短路径的数量就可以了，完全暴力。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <iostream>
#include <queue>
using namespace std;

int n, m, a, b, h[100007], cnt, dis[100007], vis[100007];
struct edge {
    int v, to, nxt;
}e[100007];
priority_queue<pair<int, int> > q;
void a_e(int u, int v) {
    e[++cnt] = (edge){1, v, h[u]}; h[u] = cnt;
    e[++cnt] = (edge){1, u, h[v]}; h[v] = cnt;
}
void dj() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    q.push(make_pair(0, 1));
    while(!q.empty()) {
        int x = q.top().second;
        q.pop();
        if(vis[x])  continue;
        vis[x] = 1;
        for(int i = h[x]; i; i = e[i].nxt) {
            int v = e[i].to, z = e[i].v;
            if(dis[v] > dis[x] + z) {
                dis[v] = dis[x] + z;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &a, &b);
        a_e(a, b);
    }
    dj();
    int maxi = 0, ans = 0;
    for(int i = 1; i <= n; ++i)
        maxi = max(maxi, dis[i]);
    for(int i = 1; i <= n; ++i)
        if(dis[i] == maxi) {
            printf("%d", i);
            break;
        }
    printf(" %d", maxi);
    for(int i = 1; i <= n; ++i)
        if(dis[i] == maxi)  ans++;
    printf(" %d", ans);
    return 0;
}