#P4331. JSOI2012 越狱老虎桥

    ID: 1827 传统题 1000ms 512MiB 尝试: 47 已通过: 22 难度: 7 上传者: 标签>难度分类提高+/省选-图论桥low-link边双连通分量桥树排序与序列处理二分答案动态规划树形 DPCF2200

JSOI2012 越狱老虎桥

[JSOI2012] 越狱老虎桥

题目背景

这里,是美丽的南京,这里,是秀美的进香河,这里是安逸的老虎桥。

如果说进香河的美,美在其秀美的风光,倒不如说是美在了那惬意的南京古典小巷式生活。如果说进香河的迷人,在其淳朴的民风,倒不如说是那被历史掩埋了的秘密吸引着人们好奇的心。

也许很多人都还记得,老虎桥监狱,北洋时期江南最大的监狱,在近一个世纪中,面对满清、北洋、民国、新中国几朝兴衰,名称屡次更替,沧桑尽显其中。

现在的人们,恐怕很难相信,到底有多少惊心动魄的事情曾经就在这里上演。

题目描述

1948 年冬,南京地下组织计划营救被困人员。老虎桥监狱有 NN 层电网,由内向外编号为 11 至 NN。第 11 层接有电源。已知 MM 条双向高压线使所有电网连通。第 ii 条高压线连接第 aia_i 层和第 bib_i 层,至少需要 TiT_i 名特工才能破坏这条线。

敌人又在某两层电网之间增设了一条高压线。这条线的两端没有列入输入,小分队也无法事先知道破坏它需要多少人。

小分队需要派出一批特工。对于新增高压线的每一种可能接法,都要能从原有高压线中选择恰好一条破坏,使得至少一层电网与第 11 层断开。不同接法下可以选择不同的线。

求至少派出多少名特工,才能应对所有可能的接法。

输入格式

第一行两个整数 N,MN,M,表示电网层数和原有高压线数。接下来 MM 行,每行三个整数 ai,bi,Tia_i,b_i,T_i,描述一条原有高压线。

输出格式

一行一个整数,表示最少需要派出的特工人数。若无法保证成功,输出 -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 说明

若新增线连接第 22 层和第 33 层,只能破坏第 11 层与第 44 层之间的线,需要 33 名特工。若新增线连接第 22 层和第 44 层,或连接第 33 层和第 44 层,则分别可以破坏通往第 33 层或第 22 层的线。派 33 名特工足以应对样例中所有可能的接法。

数据规模与约定

  • 对于 30%30\% 的数据,N≤200N\le200,M≤250M\le250。
  • 对于 70%70\% 的数据,N≤50000N\le50000,M≤100000M\le100000。
  • 对于全部数据,N≤500000N\le500000,M≤1000000M\le1000000,Ti≤100000T_i\le100000。