岛屿周长c语言,[IOI2008]Island 岛屿

桃扇骨 2022-10-14 11:56 148阅读 0赞

Description 你将要游览一个有N个岛屿的公园。从每一个岛i出发，只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛，但每座桥均可以双向行走。同时，每一对这样的岛屿，都有一艘专用的往来两岛之间的渡船。 相对于乘船而言，你更喜欢步行。你希望所经过的桥的总长度尽可能的长，但受到以下的限制。：

可以自行挑选一个岛开始游览。

任何一个岛都不能游览一次以上。

无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。

由S到D可以有以下方法：

步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离

渡船：你可以选择这种方法，仅当没有任何桥和/或以前使用过的渡船的组合可以由S走到D(当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。

注意，你不必游览所有的岛，也可能无法走完所有的桥。 任务 编写一个程序，给定N座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。 限制 2 <= N <= 1,000,000 公园内的岛屿数目。 1<= Li <= 100,000,000 桥i的长度。

Input 第一行包含N个整数，即公园内岛屿的数目。岛屿由1到N编号。 随后的N行每一行用来表示一个岛。第i 行由两个以单空格分隔的整数，表示由岛i筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度Li。你可以假设对於每座桥，其端点总是位于不同的岛上。

Output 你的程序必须向标准输出写出包含一个整数的单一行，即可能的最大步行距离。 注：

对某些测试，答案可能无法放进32-bit整数，你要取得这道题的满分，可能需要用Pascal的int64或C/C++的long long类型。

在比赛环境运行Pascal程序，由标准输入读入64-bit数据比32-bit数据要慢得多，即使被读取的数据可以32-bit表示。我们建议把输入数据读入到32-bit数据类型。 评分 N不会超过4,000。

Sample Input 7 3 8 7 2 4 2 1 4 1 9 3 4 2 3

Sample Output 24

HINT

![1791.jpg][]

N点N边，这题就是棵基环树，然后题面就是要我们求各个基环树的直径之和。

如何求基环树的直径？首先，对于一个基环树，用dfs找到它所包含的环，然后从环上各点出发，求出子树内(不经过环上各点)最长链，并且可以顺便求出子树内直径，那么整个基环树的直径可能为所有子树直径最大值。

当然，还可能有其他的情况，可能是环上两点的距离加上两点的子树内最长链。这个我们可以破环成链，翻倍后使用单调队列去维护

然后这题完全自己yy出来的，于是BZOJ跑了140MB……可能是BZOJ比较那啥吧(其他OJ都没有跑过128MB来着)

/\*program from Wolfycz\*/

\#include

\#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read()\{

int x=0,f=1;char ch=getchar();

for (;ch'9';ch=getchar())if (ch=='-') f=-1;

for (;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+ch-'0';

return x\*f;

inline void print(int x)\{

if (x>=10)print(x/10);

putchar(x%10+'0');

const int N=1e6;

int pre\[(N<<1)+10\],now\[N+10\],child\[(N<<1)+10\],val\[(N<<1)+10\];

int Frm\[N+10\],vis\[N+10\],A\[(N<<1)+10\],h\[(N<<1)+10\],v\[N+10\];

ll B\[(N<<1)+10\],F\[N+10\],Len;

int tot,Bgn,End;

void join(int x,int y,int z)\{pre\[++tot\]=now\[x\],now\[x\]=tot,child\[tot\]=y,val\[tot\]=z;\}

void insert(int x,int y,int z)\{join(x,y,z),join(y,x,z);\}

void dfs(int x,int fa)\{

if (End&&Bgn&&vis\[x\])return;

vis\[x\]=1;

for (int p=now\[x\],son=child\[p\];p;p=pre\[p\],son=child\[p\])\{

if (son==fa)continue;

if (vis\[son\])\{

End=son,Bgn=x;

//因为环上最后一条边会被扫两次，所以End和Bgn的赋值会显得有些奇怪

continue;

dfs(son,x),v\[son\]=val\[p\],Frm\[son\]=x;

void get\_F(int x,int fa)\{

ll G=0;

for (int p=now\[x\],son=child\[p\];p;p=pre\[p\],son=child\[p\])\{

if (son==fa||vis\[son\]==2)continue;

get\_F(son,x);

if (F\[son\]+val\[p\]>F\[x\])G=F\[x\],F\[x\]=F\[son\]+val\[p\];

elseif (F\[son\]+val\[p\]>G)G=F\[son\]+val\[p\];

Len=max(Len,F\[x\]+G);

ll work(int x)\{

Bgn=End=0;

dfs(x,0);

for (int p=now\[Bgn\],son=child\[p\];p;p=pre\[p\],son=child\[p\])if (son==End)v\[Bgn\]=val\[p\];

vis\[Bgn\]=2;

for (int tmp=End;tmp!=Bgn;tmp=Frm\[tmp\])vis\[tmp\]=2;

Len=0,get\_F(Bgn,0);

int m=0,head=1,tail=1;

//后面破环成链，单调队列优化，写的有点丑。。。

for (int tmp=End;tmp!=Bgn;tmp=Frm\[tmp\])get\_F(tmp,0),A\[++m\]=tmp;

A\[++m\]=Bgn,B\[1\]=0;

for (int i=1;i

for (int i=1;i<=m;i++)A\[m+i\]=A\[i\],B\[m+i\]=B\[i\]+B\[m\]+v\[A\[m\]\];

h\[head\]=1;

for (int i=1;i<=m<<1;i++)\{

while (head<=tail&&i-h\[head\]>=m)head++;

Len=max(Len,F\[A\[i\]\]+F\[A\[h\[head\]\]\]+B\[i\]-B\[h\[head\]\]);

while (head<=tail&&F\[A\[h\[tail\]\]\]-B\[h\[tail\]\]

h\[++tail\]=i;

return Len;

int main()\{

int n=read();ll Ans=0;

for (int i=1;i<=n;i++)\{

int x=read(),y=read();

insert(i,x,y);

for (int i=1;i<=n;i++)if (!vis\[i\])Ans+=work(i);

printf("%lld\\n",Ans);

return 0;

[1791.jpg]: https://www.lydsy.com/JudgeOnline/images/1791.jpg

岛屿周长c语言,[IOI2008]Island 岛屿

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 leetcode463. 岛屿的周长

相关 463. 岛屿的周长

相关 LeetCode 463. 岛屿的周长 JAVA

相关岛屿数量JAVA_LeetCode刷题 463. Island Perimeter 岛屿的周长 Java

相关岛屿周长c语言,[IOI2008]Island 岛屿

相关 463. 岛屿的周长

相关 Number of Islands（C++岛屿数量）

相关 LeetCode463. 岛屿的周长

相关 leetcode 463. 岛屿的周长(python)

相关 [LeetCode] Number of Islands 岛屿的数量