题解 P4962 【朋也与光玉】
lmrttx
2020-12-23 22:02:45
>一つ一つの光は小さくでも、たくさん集まればきっととても不思議な大きな力になるはず。
>虽然每一束光都很小，但如果聚集在一起，一定会成为不可思议的巨大力量。
本题成了我的信仰题。
来写篇状压+DFS的题解，我会尽量写好懂点的qwq。
题意：
有一张有向图，每个节点有一种颜色。要求的是走过 $k$ 个节点并收集 $k$ 种颜色的一条路径，使之最短。
分析：
发现 $k$ 很小，可以状压。
本题的一个点可以从很多的点转移得，所以求最短路时不考虑边的长度。这并不影响答案。
题目说**走过的点不可再走**，就是说走过的点无法修改，满足无后效性。
`dp[i][j]`表示节点 $i$ 的状态为 $j$ 时的路径长度。
然后就可以通过转移节点和状态进行搜索。
代码：
具体见代码吧，我觉得从代码入手更好理解。
代码加了防抄袭！
```cpp
#inludce<bits/stdc++.h>
usign namespace std;
#defnie inf 2147483647
#define maxm (1<<14)-1
int n,m,k;
int ans,color[110],a[110][110],dp[110][maxm];
void dfs(int now,int len,int s,int sum){
//节点 now,已经取的颜色种数len,状态s,路径长度sum
if(s&(1<<color[now])||ans<=sum||dp[now][s]<=sum)
//边界
return;
if(len==k){ans=sum;return;}
//搜索到就退出
dp[now][s]=sum;
//dp[now][s]的路径长度（答案）为当前值
for(register int i=1;i<=n;i++){
if(a[now][i]!=inf)
//节点没搜过就去搜
dfs(i,len+1,s|(1<<color[now]),sum+a[now][i]);
//颜色种数+1，状态改变，路径长度增加
}
}
inline int read(){//快读
int ss=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ss=(ss<<3)+(ss<<1)+(ch^48);
ch=getchar();
}
return ss*w;
}
void init(){
ans=inf;
n=read();m=read();k=read();
for(register int i=1;i<=n;i++) color[i]=read();
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n;j++) a[i][j]=inf;
for(register int i=1,u,v,ww;i<=m;i++){
u=read();v=read();ww=read();
a[u][v]=ww;
}
for(register int i=1;i<=n;i++)
for(register int j=0;j<(1<<k)-1;j++) dp[i][j]=inf;
for(register int i=1;i<=n;i++) dp[i][1<<color[i]]=0;
}//初始化
void out(){
if(ans==inf) puts("Ushio!");
else printf("%d",ans);
}//输出
int main(){
init();
for(register int i=1;i<=n;i++) dfs(i,1,0,0);
//从节点i，颜色数为1，状态0，长度0开始搜索
out();
return 0;
}
```
~~好像并不难呀！就是状态转移的二进制烦人了点...~~
希望本文能对读者有帮助，谢谢阅读qwq。