洛谷4381 [IOI2008]Island

题解 图论-基环树 NOI/NOI+/CTSC
题目链接 编辑文章

题意

给出一个基环森林,求所有基环树的直径之和。

点数 $N\le 10^6$ 。

题解

思想

先考虑求一个基环树的直径。

设 $\text{f[i]}$ 是 $i$ 向环外延伸的最长距离,直径有两种情况:

  1. 不经过环,答案为环的子树直径,即 $\mathrm{max}(\text{f[x]}+\text{f[y]}+w)$ ,其中 $x,y$ 是子树中两点,$w$ 是两点距离。
  2. 经过环,则答案为 $\mathrm{max}(\text{f[x]}+\text{f[y]}+\mathrm{len}(x,y))$ ,其中 $x,y$ 是环上两点,$\mathrm{len(x,y)}$ 是两点在环上的较长距离。

对于情况 $2$ ,直接 $O(n^2)$ 枚举肯定会爆,考虑断环成链后用单调队列优化。

将环断成原来的两倍长,从任意一个点出发,用 $\text{s[i]}$ 表示第 $i$ 个点,设编号为 $p$ ,的 $\text{f[p]}$ 值 ;用 $\text{dis[i]}$ 代表 $i$ 距离起点的距离。答案化为

$$s[x]+s[y]+dis[y]-dis[x]\tag{1}$$

枚举 $y$ ,去除已知量后答案化为

$$s[x]-dis[x]\tag{2}$$

要求 $(2)$ 最大 ,用单调队列维护就行了。

最后对于每个子树,对两种情况取最大值相加即可。

实现

  1. 先用 $\text{dfs}$ 求出每个点 $i$ 所属的子树 $\text{scc[i]}$ 。
  2. 拓扑排序找环,还可以用树形dp顺便求出 $\text{f[i]}$ 和上述情况 $1$ 。
  3. 从任意一个在环上的点出发断环成链,注意还需要找终点到起点的边。完成后将子树标记,$vis[scc[x]]=1$ 。
  4. 用单调队列求出情况 $(2)$ 的答案。注意两个点成环的重边情况需要单独考虑。
  5. long long

代码

#include<bits/stdc++.h>
#define ll long long
#define N 1000005

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to,w;
} edge[N<<1];
bool vis[N];
ll cnt,head[N],n,a,b,ans,scnt,scc[N],deg[N],mx[N],f[N],s[N],dis[N];

inline void add(ll u,ll v,ll w); //加边
void dfs(ll x); //dfs划分子树
inline void t_sort(); //拓扑排序,处理情况1
inline void dp(ll x); //处理情况2

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++)
    {
        a=read(); b=read();
        add(i,a,b);
        add(a,i,b);
        deg[i]++; deg[a]++; //度数
    }
    for (ll i=1;i<=n;i++) //划分子树
    {
        if (scc[i]) continue;
        scnt++;
        dfs(i);
    }
    t_sort();
    for (ll i=1;i<=n;i++)
    {
        if (!deg[i] || vis[scc[i]]) continue; //不在环上或该子树被访问过则跳过
        dp(i);
        ans+=mx[scc[i]]; //统计答案
    }
    return !printf("%lld",ans);
}

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(ll x) //划分子树
{
    scc[x]=scnt;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (scc[y]) continue;
        dfs(y);
    }
}

inline void t_sort() //拓扑排序
{
    queue <ll> q;
    for (ll i=1;i<=n;i++)
    {
        if (deg[i]>1) continue;
        q.push(i); //不在环上入队
    }
    while (!q.empty())
    {
        ll x=q.front(); q.pop();
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to,w=edge[i].w;
            if (!deg[y]) continue; //父节点跳过
            mx[scc[x]]=max(mx[scc[x]],f[x]+f[y]+w);
            f[y]=max(f[y],f[x]+w); //树形dp
            deg[x]--; deg[y]--;
            if (deg[y]==1) q.push(y);
        }
    }
}

inline void dp(ll x)
{
    ll st=x,id=scc[x],pcnt=0; //pcnt为环上点的个数
    vis[id]=1; //标记已处理过
    for (;;)
    {
        s[++pcnt]=f[x];
        deg[x]=0; //标记访问过
        bool flag=0; //flag表示还有下一个点
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to,w=edge[i].w;
            if (!deg[y]) continue; //不在环上或访问过
            flag=1;
            dis[pcnt+1]=dis[pcnt]+w;
            x=y;
            break;
        }
        if (!flag) break; //没有下一个点了退出
    }
    if (pcnt==2) //单独处理两点成环的情况
    {
        ll res=0;
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to,w=edge[i].w;
            if (y!=st) continue;
            res=max(res,w);
        }
        mx[id]=max(mx[id],f[st]+f[x]+res);
    }
    for (ll i=head[x];i;i=edge[i].next) //从终点到起点
    {
        ll y=edge[i].to,w=edge[i].w;
        if (y!=st) continue;
        dis[pcnt+1]=dis[pcnt]+w;
        break;
    }
    for (ll i=1;i<pcnt;i++) //扩成两倍
    {
        s[i+pcnt]=s[i];
        dis[i+pcnt]=dis[1+pcnt]+dis[i];
    }
    deque <ll> q;
    q.emplace_back(1);
    for (ll i=2;i<(pcnt<<1);i++) //单调队列得到答案
    {
        while (!q.empty() && i-q.front()>=pcnt) q.pop_front();
        if (!q.empty()) mx[id]=max(mx[id],s[i]+s[q.front()]+dis[i]-dis[q.front()]);
        while (!q.empty() && s[q.back()]-dis[q.back()]<=s[i]-dis[i]) q.pop_back();
        q.emplace_back(i);
    }
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空