Train the army (bfs finds the diameter of the tree)

Training the army problem solution

Description of topic

Han Xin’s army

no

no

n bases (No.

1

?

no

1-n

1?n) Each base consists of exactly

no

?

1

n?1

n?1 road connections, each road

i

i

i have time spent

t

i

m

e

i

time_i

timei?, if a base has only one road connecting to other bases, the base will be used to stockpile food.
When training the army, the advancing speed of the army is constant. Han Xin always selects the two farthest grain bases, and goes from one of these two bases to the other grain base. For each road, the army will repair and repair the road, which halves the time it takes to pass the road next time.
Every day, Han Xin holds two training sessions. Please calculate the total time spent on the two training sessions?

Enter a description

The first row contains integers

no

no

n. next

no

?

1

n?1

n?1 lines, each containing three integers

a

i

,

b

i

,

c

i

a_i, b_i, c_i

ai?,bi?,ci? indicates a point

a

i

a_i

ai? and

b

i

b_i

There is a road between bi?, and the time spent on this road is

c

i

c_i

ci?.

Output description

Output a decimal representing the total time spent training the army, and the result retains two decimal places.

Sample input

6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

Sample output

38.50

Data range

1

no

10000

1≤n≤10000

1≤n≤10000

1

a

i

,

b

i

no

1≤a_i,b_i≤n

1≤ai?,bi?≤n

0

c

i

100000

0≤c_i≤100000

0≤ci?≤100000

Time limit: 1 second Memory limit: 128M

Example explanation


First time: The training path is

5

?

1

?

6

?

3

5-1-6-3

5?1?6?3, time spent on the road is 22.

5

?

1

,

1

?

6

,

6

?

3

5-1, 1-6, 6-3

The three paths of 5?1, 1?6, and 6?3 halved the time.

Second time: The path to train the army is

4

?

1

?

6

?

2

4-1-6-2

4?1?6?2 with 16.5 spent on the road.

The answer is the sum of the two training times of the army, 22 + 16.5=38.5, the decimal is 38.50.

Problem solving ideas

Since this question requires changing edge weights, use bfs to solve the problem.

General idea:
1. Use chain forward star storage.
2. bfs finds the diameter.
3. Halve weight.
4. Use the modified weight, and then bfs find the diameter again.
5. sum the two diameters, and output reserve decimals.

Specific ideas:
1. Chain forward star storage.

  • Be sure to put the

    w

    w

    w (the weight array) is set to

    d

    o

    u

    b

    l

    e

    double

    Double type, because there are decimals after the weight is halved.

void add(int a,int b,int c)
{<!-- -->
ver[idx]=b,w[idx]=c,nxt[idx]=head[a],head[a]=idx + + ;
}
//...
memset(head,-1,sizeof(head));
int a,b,c;
cin>>n;
for(int i=1;i<n;i++)
{<!-- -->
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}`

2. Use breadth-first search to find the diameter of the tree

  • set up

    v

    i

    the s

    vis

    vis is the judging weight array,

    d

    i

    the s

    dis

    dis is the distance array,

    p

    r

    e

    pre

    pre is the predecessor of the node.

  • Create a queue, will

    v

    i

    the s

    vis

    vis is set to

    0

    0

    0, will

    d

    i

    the s

    dis

    dis is set to

    0

    x

    3

    f

    0x3f

    0x3f.

  • r

    o

    o

    t

    root

    The root node is enqueued, and the

    v

    i

    the s

    [

    r

    o

    o

    t

    ]

    vis[root]

    vis[root] is set as visited, set

    d

    i

    the s

    [

    r

    o

    o

    t

    ]

    dis[root]

    dis[root] is set to

    0

    0

    0.

  • If the queue is not empty, take out the head element named

    t

    m

    p

    tmp

    tmp, and perform a dequeue.

  • Traversing the edge set, let

    the y

    the y

    y is the endpoint of the edge,

    z

    z

    z is the edge weight.

  • if

    the y

    the y

    y has not been traversed, just update

    v

    i

    the s

    the y

    vis_y

    visy? for

    1

    1

    1, will

    the y

    the y

    Point y joins the team, will

    d

    i

    the s

    the y

    dis_y

    disy? Set to

    d

    i

    the s

    [

    t

    m

    p

    ]

    +

    z

    dis[tmp] + z

    dis[tmp] + z.

  • Will

    p

    r

    e

    the y

    pre_y

    prey? Set as the currently traversed

    i

    i

    i.

  • set up

    m

    a

    x

    max

    max is

    ?

    1

    -1

    ?1, set

    no

    o

    d

    e

    node

    node is

    0

    0

    0.

  • loop through

    d

    i

    the s

    dis

    dis array, if

    d

    i

    the s

    i

    dis_i

    disi? greater than

    m

    a

    x

    max

    max, then let

    m

    a

    x

    max

    max is equal to

    d

    i

    the s

    i

    dis_i

    disi?, and let

    no

    o

    d

    e

    node

    node is equal to

    i

    i

    i.

  • b

    f

    the s

    bfs

    The bfs function returns

    no

    o

    d

    e

    node

    node.

int bfs(int root)
{<!-- -->
   queue<int>q;
   memset(vis,0,sizeof(vis));
   memset(dis,0x3f,sizeof(dis));
   q. push(root);
   vis[root]=1;
   dis[root]=0;
   while(!q.empty())
   {<!-- -->
   int tmp=q. front();
   q. pop();
   for(int i=head[i];~i;i=nxt[i])
   {<!-- -->
   int y=ver[i];
   double z=w[i];
   if(!vis[y])
   {<!-- -->
   vis[y]=1;
   q. push(y);
   dis[y]=dis[tmp] + z;
   pre[y]=i;
   }
   }
   }
   int max=-1;
   int node=0;
   for(int i=1;i<=n;i++)
   {<!-- -->
   if(dis[i]>max)
   {<!-- -->
   max=dis[i];
   node=i;
   }
   }
   return node;
}

3. Halve the weight of the edge that the diameter passes through

  • set up

    the s

    u

    m

    1

    sum1

    sum1,

    the s

    u

    m

    2

    sum2

    sum2 for twice

    b

    f

    the s

    bfs

    The result of bfs (that is, finding the diameter for the first time).

  • set up

    a

    no

    the s

    ans

    ans for

    d

    i

    the s

    [

    the s

    u

    m

    2

    ]

    dis[sum2]

    The value of dis[sum2].

  • set variable

    i

    i

    i is

    the s

    u

    m

    2

    sum2

    Predecessor of sum2, variable

    w

    w

    ww

    ww for

    w

    i

    w_i

    The value of wi?.

  • use

    w

    i

    =

    w

    i

    XOR

    1

    w_i=w_i XOR 1

    wi?=wi? XOR 1 method to find the reverse edge (a tree is an undirected connected graph, there must be a reverse edge).

  • Divide these two edge weights by

    2.0

    2.0

    2.0

int sum1=bfs(1);
int sum2=bfs(sum1);
double ans=dis[sum2];
while(sum2!=sum1)
{<!-- -->
int i=pre[sum2];
double ww=w[i];
w[i]=w[i^1]=ww/2.0;
sum2=ver[i^1];
}

4. Find the diameter again.

sum1=bfs(1);
sum2=bfs(sum1);

5. Will

a

no

the s

ans

ans is summed and the decimal output is retained.

ans + =dis[sum2];
printf("%.2lf",ans);

AC Code

#include 
using namespace std;
const int N=100005;
int head[N];
int ver[2*N];
int nxt[2*N];
int idx=0;
double w[2*N];
bool vis[N];
double dis[N];
int pre[N];
int n;
void add(int a,int b,int c)
{
ver[idx]=b,w[idx]=c,nxt[idx]=head[a],head[a]=idx + + ;
}
int bfs(int root)
{
queueq;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
q. push(root);
vis[root]=1;
dis[root]=0;
while(!q.empty())
{
int tmp=q. front();
q. pop();
for(int i=head[i];~i;i=nxt[i])
{
int y=ver[i];
double www=w[i];
if(!vis[y])
{
vis[y]=1;
q. push(y);
dis[y]=dis[tmp] + www;
pre[y]=i;
}
}
}
int max=-1;
int node=0;
for(int i=1;i<=n;i++)
{
if(dis[i]>max)
{
max=dis[i];
node=i;
}
}
return node;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d", &n);
for(int i=1;i
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
add(a,b,c);
add(b,a,c);
}
int sum1=bfs(1);
int sum2=bfs(sum1);
double ans=dis[sum2];
while(sum2!=sum1)
{<!-- -->
int i=pre[sum2];
double ww=w[i];
w[i]=w[i^1]=ww/2.0;
sum2=ver[i^1];
}
sum1=bfs(1);
sum2=bfs(sum1);
ans + =dis[sum2];
printf("%.2lf",ans);
return 0;
}

Thanks for reading.