908 - Re-connecting Computer Sites

[calicratis19]

i m surprised abt the problem. it is said that it will give n-1<=m<=n*n-1/2 ,here m is the number of edges and n is the numbner of node which can be 1 <= n <= 1000000. so clearly m edges cant be stored in an array. but surprisingly there is no input where m>n.a two dimensional array of array[1000020][3] is enough to store edges and cost.

[Jehad Uddin]

In uva there are problems(such as 200,11042,935,(789,479 no test case )) of poor test cases , and this problem is also that type, the problem descripton is wrong also,

[Shafaet_du]

Whats wrong with problem description? just add the costs of first N-1 inputs,and thats the first output. find MST of last K+M inputs,thats the 2nd output.

[SyFyKid]

Nothing wrong, but we should remember that second line (aka MST of K+M edges) should be min(cost_before, cost_after).

Whats wrong with problem description? just add the costs of first N-1 inputs,and thats the first output. find MST of last K+M inputs,thats the 2nd output.

[VitezVojko]

Code: Select all

AC, Blank lines were the problem :S

I simply don't know, what am i doing wrong here, can someone please help me, or give me tricky I/O?

[c1337]

Can this question be done without using a priority queue and just using a disjoint-set data structure ?

[brianfry713]

http://en.wikipedia.org/wiki/Kruskal%27s_algorithm

[c1337]

When I add a edge to already formed MST it creates exactly 1 cycle. Traversing that cycle I need to find the maximum weight edge and delete it. But that means I need to implement a union-find-delete instead of just union-find. Is that correct or am I missing something ?

[brianfry713]

In Kruskal's algorithm, you only add edges that don't create a cycle.

[c1337]

What I meant was can this question be done by using the previously given MST and modifying it according to the new edges given to us ?That we don't use the information about all the edges

[brianfry713]

Here's how I solved it:

On this part of the input: "The set T of previously chosen high-speed lines, consisting of N-1 lines, each describing a high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers." ignore the graph, just sum the costs and print that on the first line of the testcase.

Next run Kruskal's algorithm from scratch on the graph containing the M + K edges, these two parts of the input combined: "K lines, each describing a new high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers." and "M lines, each describing one of the originally available high-speed lines, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers." Report the result on the second line of the testcase.

[chanderg_12]

Can't we add the new edges to the old MST by removing cycles as they appear?Will this greedy approach work?

[brianfry713]

I don't know, it depends on your implementation I guess. I would use an already existing simple greedy algorithm rather than trying to invent a new one. The old MST is essentially useless once you add new previously unconsidered edges. I think it would be much slower if you could get it to work at all.

[chanderg_12]

No. I mean something like Kruskal's algorithm except that we start with the given old MST and the new edges alone as the edge set to be sorted and then.....

Oh. Every time an edge threatens a cycle creation, we would again have to check the entire cycle to find out the bottleneck. But as we are already doing a traversal (to find if it is a cycle), will it be too much of an overload?

[brianfry713]

I don't know. Try to over complicate it if you want.