星球大战9 R" P; e# R1 U3 _( v
公元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组测试数据。
* u7 ]# j7 [5 i) U+ \
要求：可以利用c/c++、java等高级语言进行编程！
大家可以在这里贴出自己的程序代码，一起讨论你代码的优劣，共同提高自己的编程素养。
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |