求解决有关问题的代码，数据结构最小生成树有关问题
求解决问题的代码，数据结构最小生成树问题
It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city.
Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention.
Input Specification:
Your program must read test cases from the standard input.
The input consists of several test cases. Each case starts with a line containing 2 numbers N (1000), and M, which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers:
City1 City2 Cost Status
where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.
Note: It is guaranteed that the whole country was connected before the war.
The input ends with N being 0. That case must NOT be processed.
Output Specification:
For each test case, output to the standard output. Just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the connection if that city is conquered by the enemy.
In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space, but no extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.
就这个问题，2010成都ACM的，给出连接N个城市的图，当一个城市被占领后所有和该城市连接的路会关闭，每条路有权重，要求找出应该花最大力气保护的城市（即被占领后修路花费成本最高）求问怎么解决？我只会写路没权重时候的代码，求救
------解决方案--------------------
没有权重的时候 你是根据什么来生成最小生成树的
------解决方案--------------------
同求……看过一些C++的思路，大概意思是应该先用kruskal算法获得最小生成树，然后就不知道了……求C语言算法啊！
------解决方案--------------------
这个你可以看看http://blog.****.net/realxuejin/article/details/10522383
It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city.
Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention.
Input Specification:
Your program must read test cases from the standard input.
The input consists of several test cases. Each case starts with a line containing 2 numbers N (1000), and M, which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers:
City1 City2 Cost Status
where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.
Note: It is guaranteed that the whole country was connected before the war.
The input ends with N being 0. That case must NOT be processed.
Output Specification:
For each test case, output to the standard output. Just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the connection if that city is conquered by the enemy.
In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space, but no extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.
就这个问题，2010成都ACM的，给出连接N个城市的图，当一个城市被占领后所有和该城市连接的路会关闭，每条路有权重，要求找出应该花最大力气保护的城市（即被占领后修路花费成本最高）求问怎么解决？我只会写路没权重时候的代码，求救
数据结构
最小生成树
2010成都ACM
battle over cities
割点
------解决方案--------------------
没有权重的时候 你是根据什么来生成最小生成树的
------解决方案--------------------
同求……看过一些C++的思路，大概意思是应该先用kruskal算法获得最小生成树，然后就不知道了……求C语言算法啊！
------解决方案--------------------
这个你可以看看http://blog.****.net/realxuejin/article/details/10522383