1791: [Ioi2008]Island  Islands  

Time Limit: 20 Sec  Memory Limit: 162 MB

Submit: 908  Solved: 159

[Submit][

id=1791" target="_blank">Status]

Description

You are going to visit a place with N An Island Park . From every island i set out , Just build a bridge . The length of the bridge is in the order of Li Express . It's always shared in the park N A bridge .

Although each bridge is connected from one island to another . But every bridge can walk in both directions . At the same time , Every pair of these islands . There is a special ferry between the two islands .

As opposed to taking a boat , You prefer walking .

You want the total length of the bridge to be as long as possible , But with the following limitations . •  To be able to choose an island to visit . •  No island can be visited more than once . •  No matter what time you are, you can choose from the island where you are now S There's another island you've never been to D.

from S To D There can be the following ways : o  Walk : Only when there is a bridge between two islands is it possible . In such a case . The length of the bridge will add up to the total distance you walk ; perhaps  o  Ferry Boat : You can choose this way , Only if there is no bridge and / Or a combination of ferries that have been used can be made up of S Go to the D( When checking for reachability , You should think about all the paths . Including the islands you've visited ).  Be careful , You don't have to visit all the Islands , Or you may not be able to walk across the bridge .

Mission   Write a program , Given N Bridges and their lengths . According to the above rules , Calculate the maximum length of the bridge you can cross .

Limit  2 <= N <= 1,000,000  The number of islands in the park . 1<= Li <= 100,000,000  Bridge i The length of .

Input

•  The first line includes N It's an integer . The number of islands in the park . The island is made up of 1 To N Number . •  And then N Each line is used to represent an island .

The first i  The row consists of two integers separated by a single space , From the island i The bridge built . The first integer represents the bridge and the island at one end , The second integer represents the length of the bridge Li. You can if for each bridge , Its endpoints are always on different islands .

Output

Your program must write a single line containing an integer to standard output . The maximum walking distance you can walk .  notes 1: For some tests . The answer may not fit in 32-bit Integers . You have to get a full mark on this question , It may be necessary to use Pascal Of int64 or C/C++ Of long long type .  notes 2: In the competition environment Pascal Program , Read in by standard input 64-bit Data ratio 32-bit The data is much slower , Even if the data being read can 32-bit Express .

We suggest reading the input data into 32-bit data type .  score  N Not more than 4,000.

Sample Input

7

 3 8

 7 2

 4 2

 1 4

 1 9

 3 4

 2 3

Sample Output

24

/******************************************************************************/

The question :

Input n, then n Xing di i The line is made up of i To lead an undirected edge out , And the weight of the input side . This will make up k A connectivity map , Take two points on each graph . Maximize the length of the path between them , Please “ Maximum path ” The sum of the lengths .

Topic analysis :

First one n There will be... On the dot graph n side , And it's connected , All of it must have rings , And because of n-1 Striped n Point connected graphs ensure that graphs are connected and acyclic , The remaining edge must make “ Trees ” There is and only one ring in , So it is proved that every Unicom map is a “ Base ring tree ”, That is, a tree with only one ring .

So what we should output now is the sum of the diameters of all base ring trees ( The diameter of a tree is the longest path that a point on the tree does not repeat ).

Pictured , The diameter of this base ring tree is 11 To 5. after 3. length 71.

Answer key :

We need to deal with each base ring tree separately , First, find its ring , then dfs Find the longest path to the outside branch of each ring , So each point has a weight . And then every edge of the ring has a weight . We can make a monotonic queue dynamic rule on the ring , Find the diameter and length of base ring tree !

Of course , We determine the diameter of each tree in the dynamic gauge . But its initial value can not be assigned before the dynamic rule 0!

For example, in the following figure . The diameter doesn't go through the ring . by 13 To 6, length 79, So in dfs For the weight of a point on a ring , And don't forget to update the diameter value , Just how to update it needs a little consideration .

Realization :

First, two-way border building , And then search for random points , We've already searched a certain point , It means that this point is on the ring , And then deal with the ring . And then there's the search to find every point . Then we recursively get the Branch edge weight and the longest value . As point weights , Dynamic planning after monotonic queue optimization , Update the diameter length in the process . Monotonic queues multiply points , Then the length between the two points is less than the length of the ring .

Let me prove the monotonicity of dynamic rules .【 Very water , Skipping 】 First of all, set a point A、B、C、D Arrange in sequence , From A To D( Directed . Cannot from D To A) The length of the ring is A To D The length and plus A、D Point right and .

Don't ask me why I can't get from D To A. Because I've doubled the point , from D To second A Namely “ from D To A” 了 .

ok . Off topic . Let me summarize ,

length A To D = A Point right +A~B Side length +B~C Side length +C~D Side length +D Point right

So the length B To D Just  = B Point right +B~C Side length +C~D Side length +D Point right

What happened? ? what ? Just B Point right  > A Point right +A~B Side length , So from B To D Just like A To D optimal !

Empathy . The same in the back .

And here it is . And then the output can , Note that the input should use int, For output long long. Otherwise it will time out , Super many ,IOI2008 In the test data isl18f.in The solution comes out in seconds . But with long long  Read in , Ha ha ha ha .

Time, code complexity optimization :

It's very troublesome to find the ring. It's not correct ? At this point we can introduce a new solution , Similar to the implementation of the minimum tree to find the ring ( The above implementation method I actually AC I didn't know before ).

At the moment BZOJ No.1, you're not afraid ? If you write a constant well, it will be faster ? Just ask if you are afraid of ?

Here we need to apply some properties of this problem .

First of all, we can take the edge direction of data input as the positive direction , The opposite direction . ok .“ As a ” In the opposite direction . So every point has and only has one edge . And then we start at any point . Let's say there's no ring . Isn't it impossible to stop at all ?! And the data is limited . So at last it will be connected to some point on the existing chain , And I really want to , This point traverses forward , It's going to come back to this point in the end , It's a ring , And the directions of the previous points are all pushing towards the ring . At this time, we will traverse the other points one by one , First of all, there must not be two links in the same connection graph , So to change “ Can't stop ” The status quo of . New point traverses to the end . It must point to a point that has been traversed , So it's connected to the ring , Or the direction is to the ring .

So we can save the direction of data input as next[i]. Then save the length as len[i]. The reverse side has adjacency table storage ( I hate pointers. I write chain forward stars ).

So we just need to traverse random points , adopt next Mark all points along the way , Then traverse to a marked point , That is, we can quickly find the ring of the base ring tree . And then we're going to look at every point in the ring “-1” Mark , Forbid the following dfs Find the point ( The opposite edge preserves the edge on the ring ), So that we can go on with the next dfs We assign values to every point in the ring ( Look for the branches , Recursively find the longest length ).

That's the end of optimization , The next monotonous queue is no different from the general practice .

Be careful :

This topic dfs When recursing the solution, the system stack may explode because of too many layers , So you need to write a non recursive version of the stack dfs. I'll attach the staring out recursive version to the following code dfs In order to understand ideas .( Don't think about opening up a large system stack !

That's not as good as handwriting, not recursion dfs Well .)

/**************************************************************
Problem: 1791
User: 18357
Language: C++
Result: Accepted
Time:11052 ms
Memory:120100 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <iostream>
#define N 1050000
using namespace std;
struct Syndra
{
int u,v,len,next;
}e[N];
struct Fiona
{
int edge,flag1,flag2;
long long temp,max1,max2;
}s[N];
int head[N],cnt,n;
int visit[N],next[N],len[N];
int i,j,k;
long long sa[N],pre[N],ans;
void add(int u,int v,int len)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].len=len;
e[cnt].next=head[u];
head[u]=cnt;
}
int que[N<<1];
long long sum[N<<1],ret;
long long dp(int num)
{
int top,tail;
int u,b,star;
int et;
for(et=1;et<(num<<1);et++)
{
sum[et]=sum[et-1]+pre[(et-1)>=num?(et-1-num):(et-1)];
}
top=tail=0; que[top]=0;
for(et=1;et<(num<<1);et++)
{
while(et-que[top]>=num)top++;
u=que[top];
ret=max(ret,sa[et>=num?et-num:et]+sa[u>=num? u-num:u]+sum[et]-sum[u]);
b=que[tail];
que[++tail]=et;
for(star=tail;star>top;b=que[star-1])
{
if(sum[et]-sum[b]+sa[b>=num?b-num:b]<sa[et>=num?et-num:et])
{
que[star]=b;
que[--star]=et;
}
else break;
}
tail=star;
} /*que[tail++]=0;
for(et=1;et<(num<<1);++et)
{
while(top<tail&&et-que[top]>=num)++top;
u=que[top];
ret=max(ret,sa[et>=num? et-num:et]+sa[u>=num?u-num:u]+sum[et]-sum[u]);
while(top<tail&&sa[et>=num? et-num:et]>=sa[que[tail-1]>=num? que[tail-1]-num:que[tail-1]]+sum[et]-sum[que[tail-1]])--tail;
que[tail++]=et;
}*/
return ret;
}
void build()
{
cnt=1;
memset(head,0,sizeof(head));
memset(visit,0,sizeof(visit));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&next[i],&len[i]);
add(next[i],i,len[i]);
}
}
stack<int>sk;
int fa[N];
void dfs(int x)
{
if(s[x].edge==0)
{
sk.pop();
if(s[x].flag2)ret=max(ret,s[x].max1+s[x].max2);
if(visit[x]==-1)
return ;
x = sk.top();
{
int v,tt=s[x].edge;
v=e[tt].v;
visit[v]=i;
s[x].temp=s[v].max1+e[tt].len;
if(s[x].max1<s[x].temp)
{
if(s[x].flag1)s[x].max2=s[x].max1,s[x].flag2=1;
else s[x].flag1=1;
s[x].max1=s[x].temp;
}
else if(s[x].max2<s[x].temp)s[x].max2=s[x].temp,s[x].flag2=1;
s[x].edge=e[tt].next;
}
return ;
}
int v,tt=s[x].edge;
v=e[tt].v;
if(visit[v]==-1)
{
s[x].edge=e[tt].next;
return ;
}
fa[v]=x;
s[v].edge=head[v];
sk.push(v);
}
long long handle(int x)
{
s[x].edge=head[x];
sk.push(x);
while(!sk.empty())
{
dfs(sk.top());
}
return s[x].max1;
}/*handle(long long)+dfs(void)=dfs(long long)*/
/*long long dfs(int x)
{
int et,v,flag1,flag2;
long long max1,max2;
for(max1=max2=0,flag1=flag2=0,et=head[x];et;et=e[et].next)
{
v=e[et].v;
if(visit[v]==-1)continue;
temp=dfs(v)+e[et].len;
visit[v]=i;
if(max1<temp)
{
if(flag1)max2=max1,flag2=1;
max1=temp;
flag1=1;
}
else if(max2<temp)max2=temp,flag2=1;
}
if(flag2)ret=max(ret,max1+max2);
return max1;
}*/
int main()
{
// freopen("isl.in","r",stdin);
// freopen("isl.out","w",stdout);
int u,v;
build();
for(i=1;i<=n;i++)
{
if(!visit[i])
{
for(u=i;!visit[u];u=next[u])
{
visit[u]=i;
}
if(visit[u]==i)
{
ret=0;cnt=0;
visit[u]=-1;
for(v=next[u];v!=u;v=next[v])
{
visit[v]=-1;
}
v=u;
do{
pre[cnt]=len[v];
sa[cnt++]=handle(v);
v=next[v];
}while(v!=u);
ans+=dp(cnt);
}
}
}
cout<<ans;
return 0;
} 

Here's how to read in the optimized code , These days , You don't read optimization , Just input is slower than this code ~


/**************************************************************
Problem: 1791
User: 18357
Language: C++
Result: Accepted
Time:4556 ms
Memory:120132 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cctype>
#include <iostream>
#define N 1050000
using namespace std;
inline int getc() {
static const int L = 1<<15;
static char buf[L],*S=buf,*T=buf;
if(S==T){
T=(S=buf)+fread(buf,1,L,stdin);
if(S==T)return EOF;
}
return *S++;
}
inline int getint() {
int c;
while(!isdigit(c = getc()));
int tmp = c-'0';
while(isdigit(c=getc()))
tmp=(tmp<<1)+(tmp<<3)+c-'0';
return tmp;
}
struct Syndra
{
int u,v,len,next;
}e[N];
struct Fiona
{
int edge,flag1,flag2;
long long temp,max1,max2;
}s[N];
int head[N],cnt,n;
int visit[N],next[N],len[N];
int i,j,k;
long long sa[N],pre[N],ans;
void add(int u,int v,int len)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].len=len;
e[cnt].next=head[u];
head[u]=cnt;
}
int que[N<<1];
long long sum[N<<1],ret;
long long dp(int num)
{
int top,tail;
int u,b,star;
int et;
for(et=1;et<(num<<1);et++)
{
sum[et]=sum[et-1]+pre[(et-1)>=num?(et-1-num):(et-1)];
}
top=tail=0;
/*
que[top]=0;
for(et=1;et<(num<<1);et++)
{
while(et-que[top]>=num)top++;
u=que[top];
ret=max(ret,sa[et>=num?et-num:et]+sa[u>=num? u-num:u]+sum[et]-sum[u]);
b=que[tail];
que[++tail]=et;
for(star=tail;star>top;b=que[star-1])
{
if(sum[et]-sum[b]+sa[b]<sa[et])
{
que[star]=b;
que[--star]=et;
}
else break;
}
tail=star;
}
*/
que[tail++]=0;
for(et=1;et<(num<<1);++et)
{
while(top<tail&&et-que[top]>=num)++top;
u=que[top];
ret=max(ret,sa[et>=num?et-num:et]+sa[u>=num?u-num:u]+sum[et]-sum[u]);
while(top<tail&&sa[et>=num?et-num:et]>=sa[que[tail-1]>=num? que[tail-1]-num:que[tail-1]]+sum[et]-sum[que[tail-1]])--tail;
que[tail++]=et;
}
return ret;
}
void build()
{
cnt=1;
memset(head,0,sizeof(head));
memset(visit,0,sizeof(visit));
n=getint();
for(i=1;i<=n;i++)
{
next[i]=getint();
len[i]=getint();
add(next[i],i,len[i]);
}
}
stack<int>sk;
int fa[N];
void dfs(int x)
{
if(s[x].edge==0)
{
sk.pop();
if(s[x].flag2)ret=max(ret,s[x].max1+s[x].max2);
if(visit[x]==-1)
return ;
x = sk.top();
{
int v,tt=s[x].edge;
v=e[tt].v;
visit[v]=i;
s[x].temp=s[v].max1+e[tt].len;
if(s[x].max1<s[x].temp)
{
if(s[x].flag1)s[x].max2=s[x].max1,s[x].flag2=1;
else s[x].flag1=1;
s[x].max1=s[x].temp;
}
else if(s[x].max2<s[x].temp)s[x].max2=s[x].temp,s[x].flag2=1;
s[x].edge=e[tt].next;
}
return ;
}
int v,tt=s[x].edge;
v=e[tt].v;
if(visit[v]==-1)
{
s[x].edge=e[tt].next;
return ;
}
fa[v]=x;
s[v].edge=head[v];
sk.push(v);
}
long long handle(int x)
{
s[x].edge=head[x];
sk.push(x);
while(!sk.empty())
{
dfs(sk.top());
}
return s[x].max1;
}/*handle(long long)+dfs(void)=dfs(long long)*/
/*long long dfs(int x)
{
int et,v,flag1,flag2;
long long max1,max2;
for(max1=max2=0,flag1=flag2=0,et=head[x];et;et=e[et].next)
{
v=e[et].v;
if(visit[v]==-1)continue;
temp=dfs(v)+e[et].len;
visit[v]=i;
if(max1<temp)
{
if(flag1)max2=max1,flag2=1;
max1=temp;
flag1=1;
}
else if(max2<temp)max2=temp,flag2=1;
}
if(flag2)ret=max(ret,max1+max2);
return max1;
}*/
int main()
{
int u,v;
build();
for(i=1;i<=n;i++)
{
if(!visit[i])
{
for(u=i;!visit[u];u=next[u])
{
visit[u]=i;
}
if(visit[u]==i)
{
ret=0;cnt=0;
visit[u]=-1;
for(v=next[u];v!=u;v=next[v])
{
visit[v]=-1;
}
v=u;
do{
pre[cnt]=len[v];
sa[cnt++]=handle(v);
v=next[v];
}while(v!=u);
ans+=dp(cnt);
}
}
}
cout<<ans;
return 0;
}

Copyright notice : This article is the original article of the blogger . Blog , Do not reprint without permission .

【BZOJ1791】【IOI2008】【 Base ring tree 】island(status First speed ) More articles about

  1. bzoj1791[IOI2008]Island Islands ( Base ring tree +DP)

    Topic link :https://www.lydsy.com/JudgeOnline/problem.php?id=1791  The main idea of the topic : Here's a tree for you n Edge of the base ring tree forest , I want you to find all the base ring trees / The sum of the diameters of trees .n< ...

  2. BZOJ1791 [Ioi2008]Island Islands [ Base ring tree + Monotonic queue optimization DP]

    The diameter of base ring tree . First of all, there are only two forms of base ring tree diameter : The diameter of the tree hanging on the ring in each base ring tree , Or the sum of the distances between the maximum depth roots of two trees hanging on the ring . therefore , Run through each connected block first , Find the dots on the ring , Then run for each point on the ring ...

  3. P4381 [IOI2008]Island( Base ring tree + Monotonic queue optimization dp)

    P4381 [IOI2008]Island The question : Find the diameter sum of all base ring trees in a graph We calculate the answer for each base ring tree . First of all, let's bfs Looking for a ring (dfs The explosive stack ) After the blue, we deal with the diameter The diameter is not on the ring , It's on the subtree at some point in the ring ...

  4. [IOI2008/BZOJ1791 Islands ]( Tips for dealing with base ring trees &amp; be based on bfs Tree form DP)

    IOI2008/BZOJ1791 Islands The main idea is to find the diameter of each base ring tree in a base ring tree forest ① And . In fact, it is the base ring tree upgrade of the tree diameter . Let's find the ring first , And then from every node in the ring x set out , And it doesn't go through other nodes in the ring ...

  5. BZOJ1791[Ioi2008]Island Islands —— Base ring forest diameter and + Monotonic queue optimization DP+ Tree form DP

    Title Description You are going to visit a place with N An Island Park . From every island i set out , Just build one bridge . The length of the bridge is in the order of Li Express . There are a total of N A bridge . Although each bridge is connected from one island to another , But every bridge can walk in both directions . meanwhile , Every pair of these islands , All have one ...

  6. BZOJ 1791: [IOI2008]Island Islands - Base ring tree

    Portal Answer key The question = Find out the diameter of each base ring tree in the undirected base ring tree forest . We first need to find the ring of each base ring tree , But because it's an undirected graph , use tarjan Looking for a ring , Add a manual stack , I saw it too dalao My blog knows tarjan Find none ...

  7. bzoj 1791: [Ioi2008]Island Islands 【 Base ring tree + Monotonic queue optimization dp】

    I've been cooking all morning -- This problem requires the diameter of the base ring tree and The general step is to find the ring ->dp Find the farthest distance of each ring point as the point weight -> Double the loop , A monotonous queue dp Finding rings is topological , But the use of nature is more ...

  8. luogu 4381 [IOI2008]Island A monotonous queue + Base ring tree diameter + tarjan

    Description You are going to visit a place with N An Island Park . From every island i set out , Just build one bridge . The length of the bridge is in the order of Li Express . There are a total of N A bridge . Although each bridge is connected from one island to another , But every bridge can walk in both directions . meanwhile , Every pair is like this ...

  9. bzoj The thousand questions project 114:bzoj1791: [Ioi2008]Island Islands

    http://www.lydsy.com/JudgeOnline/problem.php?id=1791 Is to find the sum of the diameters of all base ring trees Add manual stack #include<cstdio> #incl ...

Random recommendation

  1. sql Basic operation

    SQL function Data query SELECT Data definition CREATE,  DROP,   ALTER Data manipulation INSERT,   UPDATE,   DELETE Data control GRANT,  REVOKE establish ...

  2. mysql SQL_CALC_FOUND_ROWS

    mysql> ,; +----+ | id | +----+ |   | |   | |   | |   | |   | +----+  rows  | +--------------+  ro ...

  3. mouseover And mouseenter The difference between

    mouseenter The event enters an element with the mouse , Or when you first enter a child of this element . Once triggered , stay mouseleave Before , The mouse triggers on the child element of this element mouseenter Events don't trigger this element mo ...

  4. Unobtrusive Ajax

    ASP.NET MVC And Unobtrusive Ajax( 5、 ... and )   Preface Let's talk about it in this section Unobtrusive Medium Ajax Submit , Most of the time we use JQuery To carry out Ajax request , Of course. JQue ...

  5. W3Cschool Learning notes ——CSS3 course

    towards div Element to add rounded corners : div { border:2px solid; border-radius:25px; -moz-border-radius:25px; /* Old Firefox */ ...

  6. studio Set up File Templates

    Considering the overall style of the project , Explain all classes as necessary , As far as annotation is concerned, the first thing to be explained is the author , File creation time , Business function description , These are the basic contents , Before adding these instructions, you may manually add the file title header , It's very old-fashioned now ...

  7. C# in realdonly It's not read-only

    Realdonly Many students understand it literally . Think through realdonly The modified keyword is read-only , Actually , Not exactly . Such as int.string.bool Once the basic data type is assigned , It can't be changed . But if it is ...

  8. WordPress No revision history 、 Summary of the latest methods of auto save and auto draft

    remind : Some of the methods I summarize here only support the previous versions WordPress, For the new version of WordPress, Some functions are not supported , So please make a backup before operation . my WordPress The current version is 4.3.1, I'll be effective in my test ...

  9. HTTP/2 brief introduction

    Support the existing Web Service HTTP The agreement is away from the 1997 Years have passed , And then HTTP/1.1 Version released from 1999 year . With the progress of technology and the evolution of demand , For fast and efficient data transmission ,HTTP/1 ...

  10. 【 primary 】 Use less Achieve random snow animation

    New Year's day at the company , It's interesting to think of a code for the Christmas shake project , Take the free time to pull out the code , Experience under precipitation . Winter is coming , The designers say the wobble scene requires a random falling snowflake animation , The first thing that came to mind was canvas better , Project not ...