跳到主要内容

2026.09.15 测试

修改
· 阅读需 9 分钟
laieahoy
laieahoy
管理员

C. Grass Cownoisseur​

首先，图上的问题通常第一步都是缩点（虽然我没想到），这道题也不例外，缩点之后就是一个有向无环图，那么这种将一条边反向的问题经典的思路就是建反图，然后正反从 11 跑一遍到每个点最长路，然后对于每个点连的每条边都尝试反向，路径长度也可以快速算出。

具体求路径长度时，举一个例子，假设反图从 11 到某个点 uu 的最大距离为 dis2[u]dis2[u]，取反图上的 uu 直接连接的某个点 vv，若正图上 11 到 vv 有路径且最大路径为 dis[v]dis[v]，则我们将这条边反向后，所能得到的整个路径长为 dis2[u]+dis[v]−sz[c[1]]dis2[u]+dis[v]-sz[c[1]]（c[1]c[1] 为 11 所在的强连通分量），因为 11 所在强连通分量的大小在正反图中计算路径时会被重复计算，而因为缩点，所以 uu，vv 是两个不同的强连通分量，不会有点被重复计算，所以这样计算是对的。

最后，需要处理一些边界情况，若是不翻转任意一条边，那么答案就是 sz[c[1]]sz[c[1]]。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;

const int N=1e5+5;
int n,m,ans;
int oe[N],one[N],oh[N],oidx;
int e[N],ne[N],h[N],idx;
int fe[N],fne[N],fh[N],fidx;
int dfn[N],low[N],st[N],cnt,top;
int c[N],sz[N],id;
int dis[N],dis2[N];

void add(int a,int b)
{
    oe[oidx]=b;
    one[oidx]=oh[a];
    oh[a]=oidx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    st[++top]=u;
    for(int i=oh[u];~i;i=one[i]){
        int v=oe[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!c[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        id++;
        int y;
        do{
            y=st[top--];
            c[y]=id;
            sz[id]++;
        }while(y!=u);
    }
}

void add1(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void add2(int a,int b)
{
    fe[fidx]=b;
    fne[fidx]=fh[a];
    fh[a]=fidx++;
}

void spfa1(int u)
{
    queue<int> q;
    q.push(u);
    dis[u]=sz[u];
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int v=e[i];
            if(dis[v]<dis[t]+sz[v]){
                dis[v]=dis[t]+sz[v];
                q.push(v);
            }
        }
    }
}

void spfa2(int u)
{
    queue<int> q;
    q.push(u);
    dis2[u]=sz[u];
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=fh[t];~i;i=fne[i]){
            int v=fe[i];
            if(dis2[v]<dis2[t]+sz[v]){
                dis2[v]=dis2[t]+sz[v];
                q.push(v);
            }
        }
    }
}

int main()
{
    memset(oh,-1,sizeof oh);
    memset(h,-1,sizeof h);
    memset(fh,-1,sizeof fh);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=oh[i];~j;j=one[j]){
            int v=oe[j];
            if(c[i]!=c[v]) add1(c[i],c[v]),add2(c[v],c[i]);
        }
    }
    spfa1(c[1]);
    spfa2(c[1]);
    ans=sz[c[1]];
    for(int i=1;i<=cnt;i++){
        for(int j=fh[i];~j;j=fne[j]){
            int v=fe[j];
            if(dis[i]&&dis2[v]) ans=max(ans,dis2[v]+dis[i]-sz[c[1]]);
        }
    }
    cout<<ans<<"\n";

    return 0;
}

D. 快餐店​

这张图有 nn 个点、nn 条边，并且保证连通，因此它一定是一棵树多出一条边，也就是恰好有一个环，即图是一个基环树。

删除环外的边会使图不连通，所以真正需要考虑的只有环上的边。删去其中一条边后，环就会变成一条链，问题也就转化成了：如何快速计算每条断边对应的直径。

首先用拓扑排序的方式不断删除度数为 11 的点。环外的部分都是树，删除会从叶子开始逐层进行，最后没有被删除的点恰好构成环。接着沿着环走一圈，记录环上点的顺序，以及相邻环点之间的边权。

对于每个环点，它外面挂着一棵树。我们只需要保留两个信息：

  • hih_i：从第 ii 个环点出发，向挂树中走能到达的最远距离；
  • inDiainDia：所有挂树内部直径的最大值。

其中 hih_i 可以通过树形 DP 求出。对于树上的节点 uu，设它向下的最长、次长路径分别为 x,yx,y，则：

dep[u]=xdep[u]=x

而经过 uu 的最长路径可能是：

x+yx+y

同时，直径也可能完全位于某个儿子的子树中，因此还要继承儿子的直径。

假设删去环上某条边后，环被展开成一条链。令 pip_i 表示从链的一端走到第 ii 个环点的距离。

若两棵挂树分别位于第 aa、bb 个环点，且 a<ba<b，它们的最远点之间的距离为：

ha+(pb−pa)+hbh_a+(p_b-p_a)+h_b

整理得：

(ha−pa)+(hb+pb)(h_a-p_a)+(h_b+p_b)

于是可以用前缀最大值和后缀最大值在线性时间内计算链上的最长路径。

定义：

  • pfipf_i：前缀中 hj+pjh_j+p_j 的最大值；
  • pdipd_i：前缀内两棵挂树之间的最长路径；
  • sfisf_i、sdisd_i：对应的后缀信息。

如果删除第 ii 条环边，链被分成左右两部分。此时最长路径只有三种情况：

  1. 完全位于左边，长度为 pdipd_i；
  2. 完全位于右边，长度为 sdi+1sd_{i+1}；
  3. 一端在左边，一端在右边，长度为
pfi+wk+sfi+1pf_i+w_k+sf_{i+1}

其中 wkw_k 是环上被保留下来的另一侧边，即第 kk 个环点到第 11 个环点之间的边权。

枚举每一条环边，取对应直径的最小值。最后还要和挂树内部的最大直径 inDiainDia 取最大值，因为最长路径也可能完全位于某棵挂树内部，与删去哪条环边无关。

树的中心位于直径中点，所以最终答案为：

最小直径2\frac{\text{最小直径}}2

边权为整数，直径也为整数，因此只需根据奇偶性输出 .0 或 .5。

时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n)。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
int n;
int e[N<<1],ne[N<<1],h[N],idx;
ll ww[N<<1];
int deg[N],q[N];
bool in[N];
ll cw[N];
int c[N],k;
int fa[N],ord[N],st[N];
ll dep[N],dia[N];
ll hi[N],p[N],pf[N],pd[N],sf[N],sd[N];

void add(int a,int b,ll c)
{
    e[idx]=b;
    ne[idx]=h[a];
    ww[idx]=c;
    h[a]=idx++;
}

void find_cy()
{
    int l=1,r=0;
    for(int u=1;u<=n;u++){
        in[u]=1;
        for(int i=h[u];~i;i=ne[i])
            deg[u]++;
        if(deg[u]==1){
            q[++r]=u;
        }
    }
    while(l<=r){
        int u=q[l++];
        in[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(!in[v]) continue;
            deg[v]--;
            if(deg[v]==1) q[++r]=v;
        }
    }
}

void get_cy()
{
    int s=1;
    while(!in[s]) s++;
    int u=s;
    int last=0;
    do{
        c[++k]=u;
        int use=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(in[v]&&i!=(last^1)){
                use=i;
                break;
            }
        }
        cw[k]=ww[use];
        u=e[use];
        last=use;
    }while(u!=s);
}

void tdp()
{
    int top=0;
    int os=0;
    for(int u=1;u<=n;u++){
        fa[u]=-1;
    }
    for(int i=1;i<=k;i++){
        fa[c[i]]=0;
        st[++top]=c[i];
    }
    while(top){
        int u=st[top--];
        ord[++os]=u;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(in[v]||fa[v]!=-1) continue;
            fa[v]=u;
            st[++top]=v;
        }
    }
    for(int z=os;z;z--){
        int u=ord[z];
        ll x=0;
        ll y=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(fa[v]!=u) continue;
            dia[u]=max(dia[u],dia[v]);
            ll t=dep[v]+ww[i];
            if(t>x){
                y=x;
                x=t;
            }else if(t>y){
                y=t;
            }
        }
        dep[u]=x;
        dia[u]=max(dia[u],x+y);
    }
}

ll cdp()
{
    p[1]=0;
    for(int i=2;i<=k;i++) p[i]=p[i-1]+cw[i-1];
    pf[1]=hi[1]+p[1];
    pd[1]=0;
    ll bst=hi[1]-p[1];
    for(int i=2;i<=k;i++){
        pf[i]=max(pf[i-1],hi[i]+p[i]);
        pd[i]=max(pd[i-1],bst+hi[i]+p[i]);
        bst=max(bst,hi[i]-p[i]);
    }
    sf[k]=hi[k];
    sd[k]=0;
    bst=hi[k]+p[k];
    for(int i=k-1;i;i--){
        sf[i]=max(sf[i+1],hi[i]+p[k]-p[i]);
        sd[i]=max(sd[i+1],hi[i]-p[i]+bst);
        bst=max(bst,hi[i]+p[i]);
    }
    ll ans=pd[k];
    for(int i=1;i<k;i++){
        ll cur=0;
        cur=max(cur,pd[i]);
        cur=max(cur,sd[i+1]);
        cur=max(cur,pf[i]+cw[k]+sf[i+1]);
        ans=min(ans,cur);
    }
    return ans;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1,u,v;i<=n;i++){
        ll w;
        cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    find_cy();
    get_cy();
    tdp();
    ll ind=0;
    for(int i=1;i<=k;i++){
        hi[i]=dep[c[i]];
        ind=max(ind,dia[c[i]]);
    }
    ll ans=max(ind,cdp());
    cout<<ans/2;
    if(ans&1) cout<<".5\n";
    else cout<<".0\n";

    return 0;
}