Why this algorithm is correct?

Revision en1, by 2016gdgzoi471, 2018-12-22 05:13:07

There are many ways to solve this problem problem. My code was accepted, but can anyone give me a proof of my algorithm? The process of my algorithm: 1.find the vertex u with the maximum depth. 2.If this vertex has been covered, ignore it and goto 1. 3.Find another vertex v with the minimum depth. It is an ancestor of u, and the sum of w of all the vertex on the path between u and v does not exceed S. 4.Cover all the vertex between u and v. 5.If there are still uncovered vertex, goto 1. Can anyone give me a proof of my algorithm?

Tags greedy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English 2016gdgzoi471 2018-12-22 05:15:55 8 Tiny change: 'roblem/E),the proble' -> 'roblem/E), the proble'
en4 English 2016gdgzoi471 2018-12-22 05:14:38 1 Tiny change: 'roblem/E),the proble' -> 'roblem/E), the proble'
en3 English 2016gdgzoi471 2018-12-22 05:14:19 19 Tiny change: 'problem/E) problem. My code ' -> 'problem/E),the problem E in round 514. My code '
en2 English 2016gdgzoi471 2018-12-22 05:13:30 16
en1 English 2016gdgzoi471 2018-12-22 05:13:07 621 Initial revision (published)