2003年15届国际信息学奥赛试题.pdf

2003年第15届 国际信息学奥赛试题解析 (美国) 第一题兽径管理 Trail Maintenance (interactive task) Task Farmer John9s cows wish to travel freely among the N (l=N=200) fields (n mbered 1・・・N) on the farm, even tho gh the fields are separated by forest. The cows wish to maintain trails between pairs of fields so that they can travel from any field to any other field sing the maintained trails. Cows may travel along a maintained trail in either direction. The cows do not b ild trails. Instead, they maintain wild animal trails that they have discovered. On any week, they can choose to maintain any or all of the wild animal trails they know abo t. Always c rio s, the cows discover one new wild animal trail at the beginning of each week. They m st then decide the set of trail, to maintain for that week so that they can travel from any field to any other field. Cows can only se trails which they are c rrently maintaining. The cows always want to minimize the total length of trail they m st maintain. The cows can choose to maintain any s bset of the wild animal trails they know abo t, regardless of which trails were maintained the previo s week. Wild animal trails (even when maintained) are never straight. Two trails that connect the same two fields might have different lengths. While two trails might cross, cows are so foc sed, they ref se to switch trails except when they are in a field. At the beginning of each week, the cows will describe the wild animal trail they discovered. Yo r program m st then o tp t the minim m total length of trail the cows m st maintain that week so that they can travel from any field to any other field, if there exists s ch a set of trails. Inp t standard inp t •The first line of inp t contains two space-separated integers, N a