2006年百度之星程序设计大赛复赛题目3：星球大战

厚积薄发

星球大战
& M  ^( S6 U6 J# R5 [) V1 \

公元4999年，人类科学高度发达，绝大部分人都已经移居至浩瀚的宇宙，在上千颗可居住星球上留下了人类的印记。然而，此时人类却**成了两个联盟：正义联盟和**联盟。两个联盟之间仇恨难解，时有战争。

现在，正义联盟计划要破坏**联盟的贸易网络，从而影响**联盟的经济状况，为下一次战争作好准备。**联盟由数百颗星球组成，贸易通过星球间的运输航道来完成。一条运输航道是双向的且仅连接两个星球，但两个星球之间可以有多条航道，也可能没有。两个星球之间只要有运输航道直接或间接的相连，它们就可以进行贸易。正义联盟计划破坏**联盟中的一些运输航道，使得**联盟的星球分成两部分，任一部分的星球都不能与另一部分的星球进行贸易。但是为了节省破坏行动所需的开支，正义联盟希望破坏尽量少的运输航道来达成目标。请问正义联盟最少需要破坏多少条运输航道呢？

输入格式：

输入文件包含多组测试数据。每组测试数据第一行为两个整数N和M（2≤N≤500，0≤M≤N(N-1)/2），N为**联盟中星球的数量。接下来M行，每行三个整数A、B和C（0≤A，B<N，A≠B，C>0），表示星球A和星球B之间有C条运输航道。运输航道的总数量不超过108。

输出格式：

每组测试数据输出一行，包含一个整数，表示需要破坏的运输航道的数量。

如果输入的贸易网络本来就是不连通的，则输出0。

输入样例：

3 3

0 1 1

1 2 1

2 0 1

4 3

0 1 1

1 2 1

2 3 1

8 14

0 1 1

0 2 1

0 3 1

1 2 1

1 3 1

2 3 1

4 5 1

4 6 1

4 7 1

5 6 1

5 7 1

6 7 1

4 0 1

7 3 1

输出样例：

2

1

2

说明：

共有5个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为5、10、15、30和40分，对每个测试数据集分别执行一次程序，每次必须在运行时限10秒内结束程序并输出正确的答案才能得分。

所有数据均从标准输入设备（stdin/cin）读入，并写出到标准输出设备 （stdout/cout）中。

五个测试数据集中输入N分别不大于20、50、100、200和500，各有9组测试数据。

1 j9 ]1 `' k8 P5 c: L+ a! a* E

要求：可以利用c/c++、java等高级语言进行编程！

( R$ X# c3 I5 B: ?8 V

大家可以在这里贴出自己的程序代码，一起讨论你代码的优劣，共同提高自己的编程素养。

扯淡浮伤

加油啊！！！！顶哦!!!!!