[AtCoder Beginner Contest 244]F – Shortest Good Path(DP + 图论)

发布于 2022-03-21  705 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09