Minimal spanning tree using prim's algorithm, don't know what is wrong

Question

First of all I'll state that I'm not asking for any code or complete solutions. I'll describe the problem:

You are given number of rooms in a building and number of hallways between them. Every hallway connects 2 rooms and is given a weight. It is always possible to get to any room. You are supposed to reduce the complete weight of all hallways by removing them, printing out the weight reduced.

Are these assumptions correct?:

1. The building is a graph, rooms are vertices, hallways are edges connecting them. Therefore this is an undirected connected graph.

2. You can solve this by getting the weight of graph's minimal spanning tree, then doing complete weight minus the weight of MST - the result is sum of weights of hallways that can be removed.

I have implemented Prim's algorithm for the MST and the result is correct for the example case and for any other cases of MST that I found on the internet. However, the grading server still gives me "wrong answer" with no other information. I don't know what's wrong. There are no more than 100 vertices and 5000 edges in the input so the ranges should not be a problem. The weights are integers <=200. I'm using adjacency matrix for the MTS. Example input:

5 7  
1 2 50  
2 3 40  
3 4 20  
4 5 10  
1 4 40  
3 5 30

In this case the program prints 80. The complete weight is 190, minimal weight is 110, so we can remove 190 - 110 = 80

My questions are:

1. Are there any obvious mistakes that come to your mind? Things to watch out for, why does it work for the example input etc..
2. Are there any medium sized test cases for MST on the internet that I could use to find the problem?
3. Is there any other way to solve this problem? I would happily try anything with the grading server.

I'm completely new to graphs so I may be missing something.

Answer 1

1. The building is a graph, rooms are vertices, hallways are edges connecting them. Therefore this is an undirected connected graph.
2. You can solve this by getting the weight of graph's minimal spanning tree, then doing complete weight minus the weight of MST - the result is sum of weights of hallways that can be removed.

Yes, both of these are correct (modulo the nitpick that the building is not a graph with rooms as vertices and hallways as edges, but can be viewed as such). And if you view it thus, the difference between the total weight of the original graph and the total weight of a minimum spanning tree is the maximal possible reduction of weight without making some rooms unreachable from others (i.e. making the graph disconnected).

So I see two possibilities,

1. You have a subtle bug in your implementation of Prim's algorithm that is triggered by a testcase on the grading server but not by the testcases you checked.
2. The grading server has a wrong answer.

Without any further information, I would consider 1 more likely.

Is there any other way to solve this problem? I would happily try anything with the grading server.

Since you need to find the weight of an MST, I don't see how you could do it without finding an MST. So the other ways are different algorithms to find an MST. Kruskal's algorithm comes to mind.