abc190E - Magical Ornament（bfs-状压dp）

题目大意：

给你n个点m条边 然后给出一组点集s 询问最短的点集v包含s的所有的点且v的相邻的点可以到达

题目思路：

可以看到k的值比较小

前几天在oj刚写过一个类似的k<=5

k<=5的时候只需要暴力枚举五个点的顺序然后处理两两相邻的最短路即可

这里K<=17

第一步肯定都是 处理这个k个点的单源最短路

时间复杂度O(kn)

做题训练赛边权为1的图写了个堆优化被学长发现了，所以这次直接就bfs上了 ，不过这个题我看学长代码的时候，他写的堆优化（逃）

处理完单源最短路后

这里k<=17 如果 全排列的话，时间复杂度是不允许的

17貌似又在暗示用二进制

所以就状压dp

**

dp[i][j] 表示在i状态下最后一个到达的点是j 方程为​​​dp[i|(1<<(en-1))][en] = min(dp[i|(1<<(en-1))][en],dp[i][st]+f[st][en]);​​

**

具体操作：

先枚举一种状态 然后枚举这个状态下为1的点作为最后一个到达的点 然后枚举这个状态下为0的点作为下一次到达的点

Code：

int n,m,k,p[19],vis[maxn],dist[maxn],f[22][22],id[maxn],dp[(1<<18)][19],ans = inf;vectore[maxn];void bfs(int st) { rep(i,1,n) vis[i] = 0,dist[i] = inf; queueq; q.push(st); dist[st]=0; vis[st]=1; while(q.size()) { int u=q.front(); q.pop(); for(int v:e[u]) { if(vis[v]) continue; dist[v] = dist[u]+1; q.push(v); vis[v]=1; } } rep(i,1,k) f[id[st]][i] = f[i][id[st]] = dist[p[i]];}ll qpow(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans;}int main() { n=read(),m=read(); for(int i=1 ; i<=m ; i++) { int u=read(); int v=read(); e[u].push_back(v),e[v].push_back(u); } k=read(); rep(i,1,k) p[i] = read(),id[p[i]] = i; rep(i,1,k) bfs(p[i]); rep(i,0,qpow(2,k)-1) rep(j,1,k) dp[i][j] = inf; rep(i,1,k) dp[1<<(i-1)][i] = 1; for(int i=0 ; i<=qpow(2,k)-1; i++) { for(int st=1 ; st<=k ; st++) { if((1<<(st-1))&i==0) continue; for(int en =1 ; en<=k ; en++) { if((1<<(en-1))&i) continue; dp[i|(1<<(en-1))][en] = min(dp[i|(1<<(en-1))][en],dp[i][st]+f[st][en]); } } } rep(i,1,k) ans = min(ans,dp[qpow(2,k)-1][i]); if(ans==inf) ans=-1; out(ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。