POJ 2570 Fiber Network：Floyd 算法求公司可達性，位掩碼優化

題目大意

有向圖，邊屬於某些公司（小寫字母標識，共 ≤26 家）。查詢：從 A 到 B，哪些公司自有線路可達？輸出公司字母集合或 "-"。

核心技巧：位掩碼 + Floyd

• 公司 ≤ 26 → 用 int 位掩碼表示公司集合，第 i 位 = 1 表示公司 i 有此邊
• g[u][v] 存 u→v 邊的公司位掩碼
• Floyd 遞推：g[i][j] |= g[i][k] & g[k][j]（位運算極快）

算法邏輯

公司 c 能從 i 達到 j ⇔ 存在中間點 k，使 c 能 i→k 且 c 能 k→j。位運算 & 即求交集，| 合併路徑。

完整代碼

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 205;
const int INF = 1e9;
int g[MAXN][MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        memset(g, 0, sizeof(g));
        char u[15], v[15], comp[30];
        
        // 讀邊
        while (scanf("%s %s", u, v) == 2) {
            if (u[0]=='0' && v[0]=='0') break;
            scanf("%s", comp);
            int a = 0, b = 0;
            // 這裡假設城市名映射為索引，實際需 map
            // 簡化：題目城市名 ≤10 大寫字母，可用 map 處理
        }
        
        // Floyd
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    g[i][j] |= (g[i][k] & g[k][j]);
        
        // 查詢
        while (scanf("%s %s", u, v) == 2) {
            if (u[0]=='0' && v[0]=='0') break;
            int a = 0, b = 0; // 城市名轉索引
            int mask = g[a][b];
            if (!mask) { puts("-"); continue; }
            for (char c = 'a'; c <= 'z'; ++c)
                if (mask & (1 << (c-'a'))) putchar(c);
            puts("");
        }
        puts("");
    }
    return 0;
}

完整可運行版（含城市名映射）

#include <cstdio>
#include <cstring>
#include <map>
#include <string>
using namespace std;

const int MAXN = 205;
int g[MAXN][MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        memset(g, 0, sizeof(g));
        map id;
        int cnt = 0;
        auto getId = [&](const string& s) {
            if (!id.count(s)) id[s] = ++cnt;
            return id[s];
        };
        
        char u[15], v[15], comp[30];
        while (scanf("%s %s", u, v) == 2) {
            if (u[0]=='0' && v[0]=='0') break;
            scanf("%s", comp);
            int a = getId(u), b = getId(v);
            for (int i = 0; comp[i]; ++i)
                g[a][b] |= 1 << (comp[i] - 'a');
        }
        
        for (int k = 1; k <= cnt; ++k)
            for (int i = 1; i <= cnt; ++i)
                for (int j = 1; j <= cnt; ++j)
                    g[i][j] |= (g[i][k] & g[k][j]);
        
        while (scanf("%s %s", u, v) == 2) {
            if (u[0]=='0' && v[0]=='0') break;
            int a = getId(u), b = getId(v);
            int mask = g[a][b];
            if (!mask) { puts("-"); continue; }
            for (char c = 'a'; c <= 'z'; ++c)
                if (mask & (1 << (c-'a'))) putchar(c);
            puts("");
        }
        puts("");
    }
    return 0;
}

複雜度

• Floyd：O(n^3)，n ≤ 200 → 8×10^6 操作，極快
• 位運算常數極小，實際運行 < 0.1s
• 空間：O(n^2)

關鍵點

1. 公司集合用位掩碼，轉化集合運算為位運算
2. Floyd 遞推 g[i][j] |= g[i][k] & g[k][j] 精準對應「存在中轉點 k 使公司 c 可達」
3. 城市名用 map 映射索引

此題是「位掩碼 + 圖論」經典結合，將多公司可達性問題轉化為位運算傳遞，代碼簡潔高效。