[ARC191D] Moving Pieces on Graph 题解

FFTotoro · 2025-01-27 10:06:00 · 题解

分类讨论题。令 u 到 v 的最短路长度为 \mathrm{dis}_{u,v}，规定一条路径 p 的长度为 |p|，并且设 l=\mathrm{dis}_{s,t}。

如果图中包含多条最短路径，那么答案为 2l。判断方法：检查是否存在大于 l+1 个结点 u 满足 \mathrm{dis}_{s,u}+\mathrm{dis}_{u,t}=l。以下的讨论中 s\to t 的最短路径唯一，不妨设为 p。

如果图中包含一条长度为 l+1 的路径，那么答案为 2l+1。判断方法：检查是否存在结点 u 满足 \mathrm{dis}_{s,u}+\mathrm{dis}_{u,t}=l+1。

如果 p 上存在一个结点度数 \ge 3，那么答案为 2l+2。判断方法：检查是否存在结点 u 满足 \mathrm{dis}_{s,u}+\mathrm{dis}_{u,t}=l+2\land\mathrm{dis}_{s,u}>1\land\mathrm{dis}_{u,t}>1*。以下的讨论中 p 上不存在度数 \ge 3 的结点。

*：经用户 @wuxiyi 提出，使用这种方法判断时，并不能保证 p 上一定有结点度数 \ge 3（反例：查看图片）——但是由于该方法判断出的答案均为 2l+2，所以并不影响算法的正确性。在此对该用户表示感谢！

现在有两种移动策略：

• 如果存在一条与 p 不交的、s\to t 的路径 p'，答案为 |p|+|p'_{\min}|，其中 p'_{\min} 为满足条件的、长度最短的路径。判断方法：在图中去掉 p 包含的所有边，求 \mathrm{dis}_{s,t} 即 |p'_{\min}|；

• 如果存在一个度数 \ge 3 的结点 u，不妨设 \mathrm{dis}_{s,u}\le\mathrm{dis}_{t,u} 且 \deg_u=3，与 u 相连的 3 个结点分别为 v_1,v_2,v_3，其中 v_1 在 s\to u 的最短路径上，那么可以采取如下策略（令初始时在 s 的棋子为 x，在 t 的棋子为 y）：

  • 将 x 移动到 v_2，距离为 \mathrm{dis}_{s,u}+1；
  • 将 y 移动到 v_3，距离为 \mathrm{dis}_{s,u}+l+1；
  • 将 x 移动到 t，距离为 \mathrm{dis}_{s,u}+l+1；
  • 将 y 移动到 s，距离为 \mathrm{dis}_{s,u}+1；

  故答案为 \min\{2l+4\mathrm{dis}_{s,u}+4\}。

将两种情况取较小值即可。

如果上述情况均不满足，那么无解。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,m,s,t,c=0,r=1e9; cin>>n>>m>>s>>t,s--,t--;
  vector<vector<int> > g(n),g2(n);
  for(int i=0;i<m;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  auto bfs=[&](int s,vector<vector<int> > g){
    vector<int> d(n,-1); d[s]=0;
    queue<int> q; q.emplace(s);
    while(!q.empty()){
      int u=q.front(); q.pop();
      for(int i:g[u])
        if(d[i]<0)d[i]=d[u]+1,q.emplace(i);
    }
    return d;
  }; // BFS 求最短路
  auto d0=bfs(s,g),d1=bfs(t,g);
  for(int i=0;i<n;i++)
    if(d0[i]+d1[i]==d0[t])c++;
  if(c>d0[t]+1)cout<<(d0[t]<<1)<<endl,exit(0);
  // 存在多条最短路径
  for(int i=0;i<n;i++)
    if(d0[i]+d1[i]==d0[t]+1)
      cout<<(d0[t]<<1|1)<<endl,exit(0);
      // 存在长度为 l+1 的路径
  for(int i=0;i<n;i++)
    if(d0[i]+d1[i]==d0[t]+2&&d0[i]>1&&d1[i]>1)
      cout<<(d0[t]+1<<1)<<endl,exit(0);
      // p 上存在度数不小于 3 的结点
  for(int i=0;i<n;i++)
    if(g[i].size()>2)
      r=min(r,(d0[t]<<1)+(min(d0[i],d1[i])+1<<2));
      // 存在度数不小于 3 的结点
  for(int i=0;i<n;i++)
    for(int j:g[i])
      if(d0[i]+d1[i]!=d0[t]||d0[j]+d1[j]!=d0[t])
        g2[i].emplace_back(j);
  auto d2=bfs(s,g2);
  if(~d2[t])r=min(r,d0[t]+d2[t]);
  // 判断是否存在一条与 p 不交的路径
  cout<<(r==1e9?-1:r)<<endl;
  return 0;
}