#P4331. JSOI2012 越狱老虎桥
JSOI2012 越狱老虎桥
[JSOI2012] 越狱老虎桥
题目背景
这里,是美丽的南京,这里,是秀美的进香河,这里是安逸的老虎桥。
如果说进香河的美,美在其秀美的风光,倒不如说是美在了那惬意的南京古典小巷式生活。如果说进香河的迷人,在其淳朴的民风,倒不如说是那被历史掩埋了的秘密吸引着人们好奇的心。
也许很多人都还记得,老虎桥监狱,北洋时期江南最大的监狱,在近一个世纪中,面对满清、北洋、民国、新中国几朝兴衰,名称屡次更替,沧桑尽显其中。
现在的人们,恐怕很难相信,到底有多少惊心动魄的事情曾经就在这里上演。
题目描述
1948 年冬,南京地下组织计划营救被困人员。老虎桥监狱有 层电网,由内向外编号为 至 。第 层接有电源。已知 条双向高压线使所有电网连通。第 条高压线连接第 层和第 层,至少需要 名特工才能破坏这条线。
敌人又在某两层电网之间增设了一条高压线。这条线的两端没有列入输入,小分队也无法事先知道破坏它需要多少人。
小分队需要派出一批特工。对于新增高压线的每一种可能接法,都要能从原有高压线中选择恰好一条破坏,使得至少一层电网与第 层断开。不同接法下可以选择不同的线。
求至少派出多少名特工,才能应对所有可能的接法。
输入格式
第一行两个整数 ,表示电网层数和原有高压线数。接下来 行,每行三个整数 ,描述一条原有高压线。
输出格式
一行一个整数,表示最少需要派出的特工人数。若无法保证成功,输出 -1。
样例 #1
样例输入 #1
3 2
1 2 1
2 3 2
样例输出 #1
-1
样例 #2
样例输入 #2
4 3
1 2 1
1 3 2
1 4 3
样例输出 #2
3
样例 2 说明
若新增线连接第 层和第 层,只能破坏第 层与第 层之间的线,需要 名特工。若新增线连接第 层和第 层,或连接第 层和第 层,则分别可以破坏通往第 层或第 层的线。派 名特工足以应对样例中所有可能的接法。
数据规模与约定
- 对于 的数据,,。
- 对于 的数据,,。
- 对于全部数据,,,。