题解：CF505B Mr. Kitayuta's Colorful Graph

· · 题解

\textbf{\textit{Problem}}

给定 n 个点，m 条边的无向图，每条边有颜色 c_i，共有 q 组询问 (u,v)，问题为满足下面条件的颜色数量：在 u,v 之间的所有路径中，存在一条路径，使得这条路径上所有边的颜色都是这个颜色。

## $\textbf{\textit{Idea}}

注意到 n,m\le 100 的数据范围，于是我们可以想到：对于每一次询问，直接从 u 开始做 DFS，求出到每个节点的答案。

现在问题在于：如何计算答案？我们可以在 DFS 的过程中对每个节点存储一个 book_{i,j}，表示所有到节点 i 的路径中，是否存在某一条路径上所有边的颜色均为 j。则很容易想到 book 的转移方程：（下面 u 表示当前节点，v 表示转移的节点，c 表示连接 u,v 的边的颜色）

book_{v,i}=book_{v_i}\lor (book_{u,i}\land [c=i])

如果直接对每条端点相同但颜色不同的边做上面的转移，我们会发现节点的访问标记会很混乱（因为存在一个节点被多次更新的情况），于是我们考虑将所有端点相同但颜色不同的边并在一起，将每条边的颜色 c 改为该条边并后表示的颜色集合 C。上面的转移方程就可以改成：（C 表示连接 u,v 的边的颜色集合）

book_{v,i}=book_{v_i}\lor (book_{u,i}\land C_i)

最后答案显然就是 book_{v,i} 中值为 \texttt{true} 的位数了。

让我们分析一下时间复杂度：对于 q 次询问，每次做 DFS（时间复杂度为 \mathcal O(n+m)），每次 DFS 过程中需要进行 \mathcal O(m) 的转移，因此时间复杂度为 \mathcal O(qm(n+m))，在本题中 n,m,q\le 100 的数据范围下完全可以通过。

\textbf{\textit{Code}}

Submission

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int N = 105, M = 205;

int n, m, q, u, v;
bool book[N][M], col[N][N][M];
vector<int> g[N];

void dfs(int x) {
    for(int y : g[x]) {
        bool flag = false;
        for(int i = 1; i <= m; i++) {
            if((book[x][i] && col[x][y][i]) && !book[y][i]) flag = true; 
            book[y][i] |= (book[x][i] && col[x][y][i]);
        }
        if(!flag) continue;
        dfs(y);
    }
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back(v), g[v].push_back(u);
        col[u][v][w] = col[v][u][w] = true;
    }
    cin >> q;
    while(q--) {
        cin >> u >> v;
        for(int i = 1; i <= n; i++) 
            for(int j = 1; j <= m; j++)
                book[i][j] = (i == u ? true : false);
        dfs(u);
        int ans = 0;
        for(int i = 1; i <= m; i++) ans += book[v][i];
        cout << ans << endl;
    }
} 

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int T = 1;
//  cin >> T;
    while(T--) solve(); 

    return 0;
}