CF925D 题解

· · 题解

思路

把初始开启的走廊放到一张图上，发现这张图上的简单路径一定能走，所以这张图上 1 到 n 的最短路就是一种方案，设其长度为 d。

考虑通过别的方法走到 n，发现若 (1,n) 初始关闭，那么走完第一条边后就会开启，只要再走回 1 就可以直接走到 n。那么 1\to x\to y\to 1\to n 就是一种路径，其中 (1,x),(x,y) 初始开启，(y,1),(1,n) 初始关闭，长度为 4。

由于这已经是最短的初始不完整的路径，所以若最短路长度 d\le 4，就可以直接用最短路。

分析这种路径什么时候存在，发现只要有点 y 与点 1 的距离为 2，那么就存在 x 使得 (1,x),(x,y) 初始开启，且 (1,y) 初始关闭，否则距离会变为 1。同时如果 (1,n) 初始开启，则最短路 d=1，不会再用长为 4 的路径，所以 (1,n) 初始关闭，可以确定有这样的路径。

如果没有这种路径，那么初始与 1 号点在同一个连通块中的所有点全都与 1 号点有直接连边，那么先走到 x，以 x 为新的起点寻找上一种路径，也就是 1\to x \to y\to z\to x\to n，其中 (z,x),(x,n) 初始关闭，其余初始开启，长度为 5。

考虑这种路径什么时候存在，发现同上只要有点 z 与点 x 的距离为 2 即可。那么当且仅当所有与 1 连通的点 x 都没有合法的 z 时会无解，也就是连通块内每个点都与其他所有点有连边，即这个连通块子图是完全图。

由于在完全图上每次走边都会使出发点被完全孤立开来，只会让完全图连通块越来越小，所以这种路径也不存在时就可以确定无解了。

具体寻找路径时直接遍历所有的出边即可，时间复杂度的话第一种路径时每条边只会作为 (x,y) 被搜到一次，第二种路径时 (x,y,z) 似乎相当于三元环记数那种复杂度？笔者太菜不会证。

代码

#include<iostream>
#include<vector> 
#include<queue>
using namespace std; 
const int N=3e5+10;
int n,m,fa[N],dis[N],te[N];
vector <int> edge[N]; 
queue <int> q;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v; cin>>u>>v;
        edge[u].push_back(v),edge[v].push_back(u);
    }
    q.push(n),dis[n]=1;
    while(q.size())
    {
        int u=q.front(); q.pop();
        for(int v:edge[u]) if(!dis[v]) dis[v]=dis[u]+1,fa[v]=u,q.push(v);
    } 
    if(dis[1]&&dis[1]<=5)
    {
        cout<<dis[1]-1<<'\n'; int p=1;
        while(p!=n) cout<<p<<' ',p=fa[p];
        cout<<n; return 0;
    } //原图最短路 
    for(int x:edge[1]) te[x]=1;
    for(int x:edge[1]) for(int y:edge[x]) if(y!=1&&te[y]!=1) 
    {
        cout<<4<<'\n'<<1<<' '<<x<<' '<<y<<' '<<1<<' '<<n;
        return 0;
    } //第一种 
    for(int x:edge[1])
    {
        for(int y:edge[x]) te[y]=x;
        for(int y:edge[x]) if(y!=1) for(int z:edge[y]) if(z!=x&&te[z]!=x)
        {
            cout<<5<<'\n'<<1<<' '<<x<<' '<<y<<' '<<z<<' '<<x<<' '<<n;
            return 0;
        }
    } //第二种 
    cout<<-1;
    return 0;
}