NYC 711 最舒適路線：並查集 + 雙指針滑動窗口優化

題目模型

N 個神經元，M 條通道 (邊)，每邊有速度 V。從 S 到 T 找路徑，使路徑上最大速度 / 最小速度 比值最小。輸出既約分數或 IMPOSSIBLE。

核心觀察：單調性

若固定最大速度 V_max，要最小化比值，應盡可能增大最小速度 V_min。等價於：在速度 ≥ V_min 的子圖中，S 和 T 是否連通？

算法：離線排序 + 並查集滑動窗口

1. 所有邊按速度 降序 排序
2. 枚舉左端點 i (作為 V_max)
3. 初始化並查集，從 i 向右掃描 j，加入邊直到 S-T 連通
4. 記錄比值 V[i] / V[j]，更新全局最小值
5. 下一輪 i+1 重新初始化並查集 (或優化增量維護)

為什麼正確？

• 排序後，區間 [i, j] 內速度單調遞減
• V[i] 是區間最大，V[j] 是區間最小 (因為剛好連通時加入的最後一條邊)
• 若 j 能更小 (速度更大)，說明 [i, j-1] 已連通，與 j 是首次連通矛盾

完整代碼

struct Edge { int u, v, w; };
bool cmp(Edge a, Edge b) { return a.w > b.w; }  // 降序

int fa[505];
int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, M; scanf("%d%d", &N, &M);
        vector edges(M);
        for (int i = 0; i < M; ++i)
            scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
        int S, T; scanf("%d%d", &S, &T);
        
        sort(edges.begin(), edges.end(), cmp);
        
        double best = 1e9;
        int bestMax = 0, bestMin = 1;
        
        for (int i = 0; i < M; ++i) {
            for (int k = 1; k <= N; ++k) fa[k] = k;
            
            for (int j = i; j < M; ++j) {
                int u = find(edges[j].u), v = find(edges[j].v);
                if (u != v) fa[u] = v;
                
                if (find(S) == find(T)) {
                    double ratio = 1.0 * edges[i].w / edges[j].w;
                    if (ratio < best) {
                        best = ratio;
                        bestMax = edges[i].w;
                        bestMin = edges[j].w;
                    }
                    break;  // 當前 i 下找到最小 j，無需繼續
                }
            }
        }
        
        if (best > 1e8) puts("IMPOSSIBLE");
        else {
            int g = gcd(bestMax, bestMin);
            if (bestMax % bestMin == 0) printf("%d\n", bestMax / bestMin);
            else printf("%d/%d\n", bestMax/g, bestMin/g);
        }
    }
    return 0;
}

複雜度

• 排序：O(M log M)
• 雙層循環：O(M² α(N))，M ≤ 5000 → 2.5×10⁷ 操作，5s 時限安全
• 空間：O(N + M)

優化方向 (可選)

• 雙指針 j 不回退：i 增加時 j 只增不減，配合可撤銷並查集或重構，降至 O(M α(N))
• 二分答案 + 並查集判斷連通性：O(M log M log V)