问题描述:

你将要游览一个有N个岛屿的公园。从每一个岛i出发,只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛,但每座桥均可以双向行走。同时,每一对这样的岛屿,都有一艘专用的往来两岛之间的渡船。

你希望所经过的桥的总长度尽可能的长,但受到以下的限制:
• 可以自行挑选一个岛开始游览。
• 任何一个岛都不能游览一次以上。
• 无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。

由S到D可以有以下方法:
步行:仅当两个岛之间有一座桥时才有可能。对于这种情况,桥的长度会累加到你步行的总距离
渡船:你可以选择这种方法,仅当没有任何桥或以前使用过的渡船的组合可以由S走到D(当检查是否可到达时,你应该考虑所有的路径,包括经过你曾游览过的那些岛)

输入:

第一行包含N个整数,即公园内岛屿的数目(2<=N<=1000000)
随后的N行每一行用来表示一个岛,第i 行由两个以单空格分隔的整数,表示由岛i筑的桥,第一个整数表示桥另一端的岛,第二个整数表示该桥的长度Li (1<=Li<=100000000)

输出:

输出可能的最大步行距离

思路:

由于每个点都有一条出边,所以图是一个基环树森林的形态,题目就是求每棵基环树直径之和。

回顾一下树的直径,有树形DP和两边BFS的解法。推广到基环树,同样可以用树形DP求解。首先应该分类讨论,有两种情况:一种是直径在某一棵子树上,另一种是直径经过环,连接两棵子树的最长链。第一种情况不难处理,依然是树形DP,在DP的过程中还可以求出最长链。第二种情况就稍微难一点,首先我们需要找环,这我们可以用拓扑排序,为了节省码量,我们可以拓扑排序的过程中进行DP。找出环后,我们应该如何处理?

不难想到,我们可以把每棵子树的最长链投影到环上的点上(子树根节点)作为点权,设为$f_i$。然后我们就要在环上找两个点$i,j$,使得$f_i+dis(i,j)+f_j$最大。这是一个DP的模型,我们先破环为链,然后前缀和维护两点距离,设节点$i$到节点1的距离为$g_i$。然后我们可以枚举$i$,然后求$max(f_j-g_j)$,这个我们就可以用单调队列维护,这样我们就可以在$O(n)$内求出$max(f_i+f_j+g_i-g_j)$。

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 1000005
#define LL long long
using namespace std;

int n, id, l=1, r, cnt, head[MAXN], belong[MAXN], deg[MAXN], q[MAXN*2];
LL ans, dia[MAXN], len[MAXN], f[MAXN*2], g[MAXN*2];
bool vis[MAXN];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int x, int y, LL z)
{
    edge[++cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].dis=z;
    head[x]=cnt;
    deg[y]++;
}

void dfs(int x, int id)
{
    belong[x]=id;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!belong[to]) dfs(to, id);
    }
}

void topsort()
{
    for(int i=1; i<=n; i++) if(deg[i]==1) q[++r]=i;
    while(l<=r)
    {
        int x=q[l++];
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(deg[to]<=1) continue;
            deg[to]--;
            dia[belong[x]]=max(dia[belong[x]], len[to]+len[x]+edge[i].dis);
            len[to]=max(len[to], len[x]+edge[i].dis);
            if(deg[to]==1) q[++r]=to;
        }
    }
}

void dp(int x)
{
    int y=x, tot=0;
    while(1)
    {
        bool flag=false;
        deg[y]=1; f[++tot]=len[y];
        for(int i=head[y]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(deg[to]<=1) continue;
            g[tot+1]=g[tot]+edge[i].dis;
            flag=true; y=to;
        }
        if(!flag) break;
    }
    if(tot==2)
    {
        int temp=0;
        for(int i=head[y]; i; i=edge[i].next)
            if(edge[i].to==x) temp=max(temp, edge[i].dis);
        dia[belong[x]]=max(dia[belong[x]], len[x]+len[y]+temp);
    }
    for(int i=head[y]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==x) g[tot+1]=g[tot]+edge[i].dis;
    }
    for(int i=1; i<=tot; i++)
    {
        f[i+tot]=f[i];
        g[i+tot]=g[tot+1]+g[i];
    }
    l=r=1; q[1]=1;
    for(int i=2; i<2*tot; i++)
    {
        while(l<=r && i-q[l]>=tot) l++;
        dia[belong[x]]=max(dia[belong[x]], f[i]+f[q[l]]+g[i]-g[q[l]]);
        while(l<=r && f[q[r]]+g[i]-g[q[r]]<=f[i]) r--;
        q[++r]=i;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(i, x, y);
        addedge(x, i, y);
    }
    for(int i=1; i<=n; i++) if(!belong[i]) dfs(i, ++id);
    topsort();
    for(int i=1; i<=n; i++)
    {
        if(deg[i]<=1 || vis[belong[i]]) continue;
        vis[belong[i]]=true;
        dp(i);
        ans+=dia[belong[i]];
    }
    printf("%lld\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注