[BeiJing2010组队]次小生成树 Tree

[BeiJing2010组队]次小生成树 Tree

Time Limit:10000MS  Memory Limit:65536K
Total Submit:319 Accepted:40
Case Time Limit:1000MS

Description

小 C 最近学了很多最小生成树的算法,Prim 算法、Kurskal 算法、消圈算法
等等。
正当小 C 洋洋得意之时,小 P 又来泼小 C 冷水了。小 P 说,让小 C 求出一
个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:
如果最小生成树选择的边集是 EM,严格次小生成树选择的边集是 ES,那么
需要满足:(value(e) 表示边 e的权值)

这下小 C 蒙了,他找到了你,希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M,表示无向图的点数与边数。
接下来 M行,每行 3个数x y z 表示,点 x 和点y之间有一条边,边的权值
为z。

Output

包含一行,仅一个数,表示严格次小生成树的边权和。(数
据保证必定存在严格次小生成树)

Sample Input

5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6

Sample Output

11

Hint

数据中无向图无自环;
50% 的数据N≤2 000 M≤3 000;
80% 的数据N≤50 000 M≤100 000;
100% 的数据N≤100 000 M≤300 000 ,边权值非负且不超过 10^9

Source
囧。。我知道这个题目可以用类似Tarjan的算法搞出来。但我悲剧的发现DFS在八中OJ上肯定爆栈囧。。只好用那种倍增的来做了。。反正复杂度都一样的(因为瓶颈不是这个而是MST)。。因为这样可以BFS。。
随便写个MST算出最小生成树,然后枚举每一条非树边,算出这个点在树上对应路径的最大边和次大边,如果跟最大边一样就跟新次大边,否则跟新最大边就OK了。。
用倍增的方法可以很容易的搞定这个。。
关键是TLE囧。。从AC大神牛哪里抄了份Specil Read过来。。总算过了囧。。
Code:
www.ideone.com/y9EAX

5 thoughts on “[BeiJing2010组队]次小生成树 Tree

  1. Nach einem langen Arbeitstag kommt man endlich in die Nähe seines Sofas, nur um auf dem letzten Meter festzustellen, dass man seinen Wohnungs nicht mehr bei sich hat. Ein Durchsuchen der Tasche führt nur zu der Erkenntnis, dass man den entweder irgendwo verloren oder vergessen hat. Vielleicht wurde er auch geklaut, doch wenn Portemonnaie und Handy noch in der Tasche sind, dann ist dies eher unwahrscheinlich. Wer seine Wohnung in einem solchen Fall doch noch irgendwann wieder betreten möchte, der muss einen rufen, wenn er nicht irgendwo einen Ersatz versteckt hat. Die Suche Die Suche nach einem ist dank des Internets denkbar einfach und es reicht, wenn man bei Google zum Beispiel nach sucht. Direkt werden alle in Frage kommenden e angezeigt, so dass man nur noch einen davon rufen muss. Wichtig ist aber, dass man nichts überszt, denn auch die Preise von en sollten verglichen werden. So ist es zum Beispiel von Vorteil für den Kunden, wenn der keine Anfahrtskosten berechnet. Auch bieten viele gute e ihre Leistungen zu Festpreisen an, so dass man genau weiß, was man im Endeffekt bezahlen muss.

  2. I often visit your website and have noticed that you don’t update it often. More
    frequent updates will give your blog higher authority & rank in google.

    I know that writing posts takes a lot of time, but you can always help yourself with miftolo’s
    tools which will shorten the time of creating an article
    to a couple of seconds.

Leave a Reply to MargieJuicy Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>