P9834 题解

· · 题解

[USACO05OPEN] Around the world G 题解

广度优先搜索+哈希

题意比较清楚了，要求一条回路，使得路径权值（这里边权定义为飞行跨过的经度，顺时针为正，逆时针为负）大于等于 360 的同时经过的边数最少。

第一眼可能会联想到最短路，但是我们首要任务是能环球一圈，而且最后求的是一条回路，明显不会跟最短路挂钩。既然要维护这么多信息，答案最后又只与边数有关，那我们当然可以祭出 BFS 大法。当然，我们必须加一点优化以保证复杂度。考虑答案的回路，显然一定是一个环（自己画画图）。并且，如果有两条路径能使得从 1 到 u 的路径权值和为 w，且 u 在答案的环上时，我们一定贪心选择边数少的路径。所以容易想到我们需要哈希存储搜索过的状态 (u,sta)，表示到达 u 时路径权值为 sta。不用存储边数，因为明显地，在搜索时遇到已有状态说明有路径捷足先登了，且因为是 BFS，另一条路径一定不劣于当前路径，自然不会再次入队。当再次搜回 1 且当前路径权值和已不低于 360，就可以放心返回答案。否则所有状态都已搜过，搜索队列已为空则返回 -1。

搜索的复杂度一直是玄学，所以这里分析一下上界。因为路径不会有回头路，而对于一条边 (u,v) 而言，最多会从 u 到 v 搜一遍，然后可能从 v 到 u 搜一遍，共经过两遍。所以上界大概在 O(n+m)，常数很小，实测能跑 70ms。注意选择 map 哈希时需要重载一下小于号。最后提醒一下计算边权时记得特判一下跨子午线的两点真实经度跨度，而且题目中相同经度的农场一样视作不同。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+10;

int n, m, jd[N], h[N], ne[N*10], e[N*10], w[N*10], idx;
struct node{
    int u, w;
    bool operator < (const struct node &x) const{return u == x.u ? w < x.w : u < x.u;};
};
struct Node{node x; int d;};
queue<Node> que;
map<node, bool> vis;

void add(int a, int b) {
    ne[++ idx] = h[a]; h[a] = idx; e[idx] = b;
    if (abs(jd[b]-jd[a]) < 180) w[idx] = jd[b]-jd[a]; 
    else {
        if (jd[b] < 180) w[idx] = jd[b] - jd[a] + 360; 
        else w[idx] = jd[b] - jd[a] - 360;
    }
}

int BFS() {
    node st = {1, 0}; que.push({st, 0}); vis[st] = 1;
    while (!que.empty()) {
        Node now = que.front(); que.pop();
        int u = now.x.u, sta = now.x.w, dis = now.d;
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v == 1 && sta + w[i] >= 360) return dis+1;
            node tmp = {v, sta + w[i]};
            if (vis[tmp]) continue;
            que.push({tmp, dis+1}); vis[tmp] = 1;
        }
    }
    return -1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", jd+i);
    for (int i = 1; i <= m; i ++) {
        int u, v; scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }
    printf("%d", BFS());
}