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
#includeusing 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) { queue 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 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; }