专栏文章

题解：P5683 [CSP-J2019 江西] 道路拆除

小小陈同学cyh
P5683题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqosv4u
此快照首次捕获于
2025/12/04 08:17
3 个月前
此快照最后确认于
2025/12/04 08:17
3 个月前
查看原文
似乎dis本来就不用上下标吧

题意：

给定一个 nn 个点 mm 条边的无向图，问最多能删去多少边，能依旧使得 11 到 s1s1 的距离不大于 t1t1 并且 11 到 s2s2 的距离不大于 t2t2。
如果不能，输出 −1-1。

样例

思考

最后剩下的边一定构成一棵树，因为所有的环显然都是可以删掉至少一条边的，让我们来思考一下这棵树是什么形状吧。
结果：最后一定是三条链 1→x,x→s1,x→s21 \rightarrow x,x \rightarrow s1,x \rightarrow s2 答案就是 m−dis1,x−disx,s1−disx,s2m-dis_{1,x}-dis_{x,s1}-dis_{x,s2} 了。
调整法证明：若存在 yy 使得 dis1,y+disy,s1+disy,s2dis_{1,y}+dis_{y,s1}+dis_{y,s2} 变小就用 yy 代替 xx 就好了。
注意枚举 xx 时要做好初始化，用 bfs 可以轻松做到 O(n+m)O(n+m) 的单源最短路，一共枚举 nn 次，且 n,mn,m 同阶，时间复杂度显然是 O(n2)O(n^2) 的。

核心代码

马蜂奇特
代码将 disdis 压成了一维虽然这毫无作用
CPP
void addedge()
{
	int x=in(),y=in();
	cnt++;
	edge[cnt].to=y;
	edge[cnt].nextt=head[x];
	head[x]=cnt;
	cnt++;
	edge[cnt].to=x;
	edge[cnt].nextt=head[y];
	head[y]=cnt;
}
void bfs(int pos)
{
	for (int i=1;i<=n;i++) vis[i]=false,f[i]=1e9;
	f[pos]=0;p=1;q[p]=pos;last=1;vis[pos]=true;
	while (p<=last)
	{
		for (int i=head[q[p]];i;i=edge[i].nextt)
		{
			if (!vis[edge[i].to])
			{
				f[edge[i].to]=f[q[p]]+1;
				vis[edge[i].to]=true;
				last++;
				q[last]=edge[i].to;
			}
		}
		p++;
	}
}
signed main()
{
	n=in();m=in();
	for (int i=2;i<=n;i++) f[i]=-1;
	for (int i=1;i<=m;i++) addedge();
	s1=in();t1=in();s2=in();t2=in();
	bfs(1);
	for (int i=1;i<=n;i++) f1[i]=f[i];
	if (f[s1]>t1||f[s2]>t2)
	{
		cout<<-1;
		return 0;
	}
	for (int i=1;i<=n;i++)
	{
		bfs(i);
		if (f1[i]+f[s1]<=t1&&f1[i]+f[s2]<=t2) ans=min(ans,f1[i]+f[s1]+f[s2]);
	}
	cout<<m-ans;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...