POJ 3687 Labeling Balls：拓撲排序與優先隊列求字典序最小解

問題背景

有 N 個球，重量互不相同，從 1 到 N。需給它們貼上 1~N 的標籤，滿足 M 條約束：「標籤 a 的球比標籤 b 的球輕」。求滿足條件的標籤對應重量序列；若有多解，輸出字典序最小的（即標籤 1 的重量最小，其次標籤 2……）；無解輸出 -1。

核心觀察

這是一個拓撲排序變體。普通拓撲排序取入度為 0 的點，但這裡要求「輕的在前，重的在後」，且字典序最小。反向思考：從最重的球開始分配。將圖的邊反向（b → a 表示 b 比 a 重），則出度為 0 的點是當前最重的球。用大根堆（優先隊列）維護出度為 0 的點，每次取出最大編號，賦予當前最大剩餘重量。這樣較輕的球（小編號）會盡早被分配到較小的重量，實現字典序最小。

算法流程

1. 建圖：讀入約束 a b，添加有向邊 b → a（b 比 a 重），並記錄出度 out[a]++。
2. 初始化：將所有 out[i] == 0 的點放入大根堆。
3. 權重分配：當前權重 w = N 遞減至 1。堆非空時，取出頂點 u，設 weight[u] = w--。遍歷 u 的入邊（即原圖中指向 u 的點 v），out[v]--，若 out[v] == 0 入堆。
4. 檢查：若分配完 w > 0 則有環，輸出 -1；否則按標籤 1~N 輸出 weight[i]。

代碼實現 (C++)

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 210;
int map[MAXN][MAXN], out[MAXN], weight[MAXN];
int main() {
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        memset(map, 0, sizeof(map));
        memset(out, 0, sizeof(out));
        for (int i = 0; i < m; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            if (!map[b][a]) { map[b][a] = 1; out[a]++; } // 反向邊 b->a
        }
        priority_queue q;
        for (int i = 1; i <= n; ++i) if (out[i] == 0) q.push(i);
        int w = n;
        while (!q.empty()) {
            int u = q.top(); q.pop();
            weight[u] = w--;
            for (int v = 1; v <= n; ++v) if (map[u][v]) {
                if (--out[v] == 0) q.push(v);
            }
        }
        if (w > 0) printf("-1\n");
        else {
            for (int i = 1; i <= n; ++i) {
                if (i > 1) printf(" ");
                printf("%d", weight[i]);
            }
            printf("\n");
        }
    }
    return 0;
}

複雜度分析

• 時間：O(N² + M log N)，N ≤ 200，M ≤ 40000，完全可行。
• 空間：O(N²) 存圖。

關鍵點總結

• 邊反向 + 出度為 0 入堆，模擬「從重到輕」分配。
• 大根堆保證同層級取大編號，使小編號獲得小權重 → 字典序最小。
• 檢測環：權重未分配完說明有環。

這題是拓撲排序在「字典序最小/最大」變體中的經典應用，反向建圖配合優先隊列是核心技巧。