[ UPD : Solved . The process what i am thinking worked . Just left the point of removing edges. just take the cost of Airports if any edges cost is equal / greater than "Cost of Airport " ]
Can someone please Give some Idea about How can I solve this Problem ?? Please help .
Link :http://www.lightoj.com/volume_showproblem.php?problem=1059
I know that's a MST problem . And I found some point of Placing Airports . My idea is :
- I will run a MST .
- If the MST is able to connect all the Nodes then I Place just One Airport initially. And Then if the Cost of an Edge is Greater than or equal to the " Cost of Making an Airport " then I will place another Airport there & then Remove the Edge's Cost.
- If the is not able to connect all the Nodes then I Place an Air Port where the Parent of a Node is Equal to the Node itself including if the Cost of an Edge is Greater than or equal to the " Cost of Making an Airport " then I will place another Airport there & then Remove the Edge's Cost.
Am I Correct ?
If I am not Correct then Please give some Idea where am I doing Mistakes ???
If Correct Then Please Give some suggestion about How Can I do this regarding the Following Points :
i) Do I have to Check all Edges ( If there is Repetition of an Edge Multiple times with Several Cost ) or i just Have to Check (n-1) edges ??
ii) How can I place The Airports if the Cost of an Edge is Greater than or equal to the " Cost of Making an Airport " & Remove the edges Adjacent to it with Same/ Greater Cost .
Please help..
[ My English is Bad. Sorry for that ]
You should try to build a MST. You'll end up with 1 or more trees, 1 in case all nodes are connected and many otherwise. Now you should place one airport in each tree and sum the costs.
I couldn't understand the step 3 of your idea but the steps 1 and 2, with a few adaptations, are similar to the process I described in last paragraph. The biggest difference being the intent to replace some edges by airports, that isn't necessary if you filter them when reading the input.
Some thoughts about the points raised:
i) You should check edges untill all vertices are connected or there are no more edges to check. Using Kruskal's algorithm you sort the edges by value and just include an edge in the MST if it connects vertices not connected yet, so repetition of edges isn't a problem.
ii) It's better to just consider as valid cheap edges, with cost smaller than the value to build an airport, to avoid dealing with replacing some of them.
This is the code I used: Don't click me