题解：P4796 [BalticOI 2018] 路径
P4796 [BalticOI 2018] 路径
- 方法：记忆化搜索。
- 首先根据题意，可以先打个暴搜，可以得到
70 分。 ::::success[暴力搜索]il void dfs(int u,int fa){ if(vis[a[u]]) return ; vis[a[u]]=1; if(fa) ++ans; for(int v:g[u]){ if(v==fa) continue; dfs(v,u); } vis[a[u]]=0; }::::
- 然后考虑优化，注意到一个点可能会遍历多次，并且状态可能一致（即相同颜色集合），考虑用记忆化数组存储，第一维表示点，第二维表示颜色集合，由于
k \le 5 ，可以用状压来表示，转移可以用以下式子表示：f_{i,S}=1 + \sum_{(i,j) \in E,a_j \notin S} f_{j,S \cup a_j} - 最后答案就是
\sum_{i=1}^n f_{i,a_i}-n ，因为路径长::::success[code] ```cpp line-numbers #include<bits/stdc++.h> #define il inline using namespace std; typedef long long ll; typedef pair<int,int> pii; il ll read(){ ll x=0;bool f=0;char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();} while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return f?-x:x; } const int N=3e5+5; int a[N]; vector<int> g[N]; ll mem[N][1<<5]; int n,m,k; il void solve(); int main() { // freopen("path.in","r",stdin); // freopen("path.out","w",stdout); solve(); return 0; } il ll dfs(int u,int fa,int val){ if((val&(1<<(a[u]-1)))||a[u]>k) return 0; int p=val|(1<<(a[u]-1)); if(mem[u][p]!=-1) return mem[u][p]; ll res=1; for(int v:g[u]){ if(v==fa) continue; res+=dfs(v,u,p); } return mem[u][p]=res; } il void solve(){ n=read(),m=read(),k=read(); memset(mem,-1,sizeof(mem)); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1,u,v;i<=m;++i) u=read(),v=read(), g[u].push_back(v),g[v].push_back(u); ll ans=0; for(int i=1;i<=n;++i) ans+=dfs(i,0,0); printf("%lld\n",ans-n); } ``` :::: 完结撒花。