A Graph Problem

[whocares21]

Cityplan: http://img705.imageshack.us/img705/2230/aoa.png

Economic crisis affected many countries. X Country is one of these countries. The government wants to make some savings. In the cities of X Country, street lights are turned on all night. The cost of a turned on street light is 1 xDollars. The government decides to turn off some lights but they still want to establish a safe, peaceful environment. Therefore, the government wants to supply at least one lighted road from a crossroad to another crossroad even if the road is not the shortest path between the crossroads. Roads consist of one or more streets. Crossroads connect the streets to each other. Streets are dual carriageway; cars both go and come back from a street.

You are going to be given a city plan of some cities in X Country which holds crossroads and number of lights on the streets. By supplying the restriction of the government maximum how many xDollars can be saved for a day?

City plan documentation format:
A city consists of m crossroads and n streets. You are going to be given an input file called “cityplan.txt”. The first line of the input file holds the numbers of m and n respectively. The following lines hold mi. and mj. crossroads and the number of the lights on the street between these crossroads (i != j).
As an output, print the lighted streets by representing them with crossroads that they connect. Give the total savings in xDollars, and calculate and print the percentage of gain. In the last line, give the running time of the algorithm in milliseconds. You can run the algorithm for 1000 times in order to obtain a statistically significant value.

Cityplan: http://img705.imageshack.us/img705/2230/aoa.png

Input file format: (cityplan.txt) 
7   11 
0   1   7 
0   3   5 
1   2   8 
1   3   9 
1   4   7 
2   4   5 
3   4   15 
3   5   6 
4   5   8 
4   6   9 
5   6   10

Output format: 
0   1 
0   3 
1   4 
2   4 
3   5 
4   6
Total savings: 50 xDollars
Total gain: (39 / 89) 43.82 %
Running time: 5 ms

------

Mates, i just need a little brain-storm about the algorithm.. Please do you comments:)

[m4ster r0shi]

It looks like you are asked to find a (minimum?) spanning tree of your
city graph -> http://en.wikipedia.org/wiki/Minimum_spanning_tree

[whocares21]

Maybe.. MST schedule= If we let say start point is 2=>
2-->4-->1-->0-->3-->5-->4-->6

but, is it the correct form of MST? i dont know... any C++ algorithm..?

[m4ster r0shi]

Well, even if this is a MST of this particular city graph, my guess is that
you'll have to write something that works for any (connected) city graph.

I'm sure you can find good C++ implementations of the three algorithms mentioned in wikipedia (Boruvka's, Prim's, Kruskal's) if you google using the right keywords, but I believe it would be better for you to pick one of them, try to understand how it works by reading the pseudo code and then try to implement it yourself.

[whocares21]

i found somethings about i cant compile anything of them.
ex: http://www.syntax-example.com/Code/implement-prims-algorithm-solve-minimum-793.aspx

i just copied and pasted but there are lots of error... i use both DevCpp and code::blocks.. :\

[m4ster r0shi]

This code is ancient and non-standard (btw, DevCpp is ancient too).
And while you could modify it to make it work, I'd suggest googling again.