CF131D Subway 题解

hzoi_Shadow · 2023-10-02 17:41:14 · 题解

题目传送门

前置知识

强连通分量 | 最短路

解法

考虑用 Tarjan 进行缩点，然后跑最短路。

• 缩点：本题的缩点有些特殊，基于有向图缩点修改而得，因为是无向图，所以在 Tarjan 过程中要额外记录一下从何处转移过来，防止在同一处一直循环。
  • 基环树上找环还有其他方法，详见 luogu P8655 [蓝桥杯 2017 国 B] 发现环，这里仅讲解使用 Tarjan 求解。
• 最短路：因为缩完点后就形成了一棵树，且因为是无向图，环外任意一点到环上最短距离等同于环上到环外任意一点最短距离，所以接着以环缩成的点为起点跑单源最短路或 DFS 或 LCA 求解即可。本篇题解使用 Dijkstra 算法求单源最短路。
  • 用 LCA 有些杀鸡用牛刀了。
    • luogu P2783 有机化学之神偶尔会做作弊 需要用到 LCA 求解。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define sort stable_sort 
#define endl '\n'
struct node
{
    int nxt,to,w;
}e[10000];
int head[10000],u[10000],v[10000],dfn[10000],low[10000],ins[10000],c[10000],dis[10000],vis[10000],cnt=0,tot=0,ans=0,scc=0,rt=0;
stack<int>s;
void add(int u,int v)
{
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=1;
    head[u]=cnt;
}
void tarjan(int x,int fa)
{
    int i,k=0;
    tot++;
    dfn[x]=low[x]=tot;
    ins[x]=1;
    s.push(x);
    for(i=head[x];i!=0;i=e[i].nxt)
    {
        if(e[i].to!=fa)
        {
            if(dfn[e[i].to]==0)
            {
                tarjan(e[i].to,x);
                low[x]=min(low[x],low[e[i].to]);
            }
            else
            {
                if(ins[e[i].to]==1)
                {
                    low[x]=min(low[x],dfn[e[i].to]);
                }
            }
        }
    }
    if(dfn[x]==low[x])
    {
        ans++;
        scc=0;
        while(x!=k)
        {
            k=s.top();
            ins[k]=0;
            c[k]=ans;
            scc++;
            s.pop();
        }
        if(scc>=2)
        {
            rt=ans;
        }
    }
}
void dijkstra(int s)
{
    int x,i;
    priority_queue<pair<int,int> >q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(make_pair(0,-s));
    while(q.empty()==0)
    {
        x=-q.top().second;
        q.pop();
        if(vis[x]==0)
        {
            vis[x]=1;
            for(i=head[x];i!=0;i=e[i].nxt)
            {
                if(dis[e[i].to]>dis[x]+e[i].w)
                {
                    dis[e[i].to]=dis[x]+e[i].w;
                    q.push(make_pair(-dis[e[i].to],-e[i].to));
                }
            }
        }
    }
}
int main()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>u[i]>>v[i];
        add(u[i],v[i]);
        add(v[i],u[i]);
    }
    for(i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            tarjan(i,0);
        }
    }
    cnt=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    for(i=1;i<=n;i++)
    {
        if(c[u[i]]!=c[v[i]])
        {
            add(c[u[i]],c[v[i]]);
            add(c[v[i]],c[u[i]]);
        }
    }
    dijkstra(rt);
    for(i=1;i<=n;i++)
    {
        cout<<dis[c[i]]<<" ";
    }
    return 0;
}    

后记

推销一下自己的 Tarjan 学习笔记 。