题目传送门:F - Shortest Good Path (atcoder.jp)
啊shit,这题没做出来啊。这个dp状态属实想不到,之前写了好几次dfs都T了,看了题解才明白,用bfs好多了。
dfs无法保证第一个拓展到的点是长度最短的,但是bfs可以,然后下一次就不会拓展已经拓展了的点。于是bfs的复杂度比dfs低了很多。
题目大意
有一个N个点,M条无向边,现在有2^N条线路,分别是0 ~ N - 1的二进制表示,比如0010表示编号为12 4的点走了偶数次,编号为3的点走了奇数次,数据保证一定存在这么多条路径。
求满足数字(0~2^N - 1)条件的路径的最小长度的和,举个例子,要满足101的路径可能是1->2->3->2,长度为4,要满足000的路径长度就是0。
思路
还是一个dp题,和E题《[AtCoder Beginner Contest 244]E – King Bombee(DP动态规划) – ErikTse Runtime》有异曲同工之妙。
但是F题的dp并不是循环可以做的dp,其实是一个bfs做的dp。
dp[i][j]的含义:dp[终点][路径],这里的路径S(S是一个0~2^N - 1的数字)用一个十进制数表示,因为N最大是17,所以开十几万大小就够了。
dp数组初始化为inf,或者-1也行,表示没走到过。
那么容易得到状态转移方程:

因为从U走到V,这里的路径变化就是V所在的二进制位异或了一个1,就如上述公式一样的变化。
我们的二进制位的第0位表示路径的1号点,也就是i位表示i+1号点,所以需要V - 1。
最后在统计答案的时候,需要对每个要求路径(1~2^N - 1)求一下终点为1~N的所有可能的最小长度,再将所有要求路径求和即可。
代码中注释比较详细。
代码
#include <bits/stdc++.h> #define sc scanf #define pr printf #define fi first #define se second #define pb push_back #define int long long using namespace std; typedef pair<int, int> PII; const int maxn = 2e5 + 10,inf = 1e8; int N, M; vector<int> g[maxn];//存图 int dp[18][maxn];//dp[终点][路径] void bfs(int u,int s) { queue<PII> q; q.push({u, s});//终点,路径 dp[u][s] = 0;//初始化dp while(!q.empty()) { int U = q.front().fi, S = q.front().se;q.pop();//提取信息,记得pop for(auto V : g[U]) { int nS = S ^ (1 << (V - 1));//算出下一个点的路径 if(dp[V][nS] != -1)continue;//BFS保证第一次更新到的点一定是长度最小的,所以如果更新过就不要再更新了 dp[V][nS] = dp[U][S] + 1;//状态转移 q.push({V, nS}); } } return; } signed main() { cin >> N >> M; for(int i = 1;i <= M; ++ i) { int x, y;cin >> x >> y; g[x].pb(y);g[y].pb(x);//双向存图 } for(int i = 1;i <= N; ++ i)g[0].pb(i);//存从0开始到所有正整数的边,方便从0开始bfs for(int i = 0;i < (1 << N); ++ i) for(int j = 0;j <= 17; ++ j)dp[j][i] = -1;//初始化dp数组 bfs(0, 0); int ans = 0; for(int i = 1;i < (1 << N); ++ i)//i为路径 { int tmp = inf; for(int j = 1;j <= N; ++ j) tmp = min(tmp, dp[j][i]); ans += tmp; } pr("%lld\n",ans); return 0; }
Comments NOTHING