题解：P4796 [BalticOI 2018] 路径

Imerance1018 · 2025-11-26 21:05:15 · 题解

由于颜色数很少，路径长度不会超过 k。

考虑 DP，定义 f_{i,j,S} 表示钦定还要走 i 条边，当前在节点 j，已经走过的颜色集合为 S 的路径数。转移顺序不好确定，使用记忆化搜索。统计答案时枚举每个起点与路径长度即可。时空复杂度 O(nk2^k)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+10;
int n,m,tot,col[N];
vector<int>G[N];
ll f[5][N][1<<5],ans;
bool vis[5][N][1<<5];

ll dfs(int i,int j,int k)
{
    if(vis[i][j][k])return f[i][j][k];
    if(i==0)return 1;
    vis[i][j][k]=1;
    for(auto nxt:G[j])
    {
        if(k&(1<<col[nxt]))continue;
        f[i][j][k]+=dfs(i-1,nxt,k|(1<<col[nxt]));
    }
    return f[i][j][k];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>tot;
    for(int i=1;i<=n;i++)cin>>col[i],col[i]--;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<tot;j++)
            ans+=dfs(j,i,1<<col[i]);
    cout<<ans<<"\n";
    return 0;
}