Problem 107

[mynameisalreadytaken]

It doesn't matter how the nodes and connections are positioned.

[Fogmeister]

Cool, thanks, realised that as I was typing the question

Solved it now though and all on my own. I came up with the algorithm myself and it works in around 15ms

Just looking up the different names and it appears I used a reverse-delete algorithm

Very pleased with this one

[amidar1]

Can anyone verify some results concerning the network that daniel.is.fischer posted a while ago?

I'm getting an initial weight of 219 and a reduced weight of 119 for his network. Hopefully this is wrong and will help me figure out why I'm not getting the right answer to the problem. (I do get the right answer for the example, though.)

Thanks!

[thundre]

Can anyone verify some results concerning the network that daniel.is.fischer posted a while ago?

I'm getting an initial weight of 219 and a reduced weight of 119 for his network.

That is correct, according to my algorithm. You must have a different problem than the one he was trying to illustrate.

[amidar1]

Oh well, I'll have to dig deeper then. Thanks for confirming the result about the test case.

Cheers

EDIT
Found the "bug." I was reading the question wrong. Very frustrating, but at least I have the answer now.

[Yfke]

I'm really stuck on this one.

I first thought that maybe the algorithm that I came up with was wrong since I just tried it for the example graph and it seemed to work, but then after some googling I found that it had a name and is a 'real' algorithm. As it turns out, I'm using the same one as the Fogmeister (not sure if the name of that algorithm should be posted in this topic though? It's quite a big giveaway).

Anyway, my program runs correctly on the example (returning 150 as the answer) and the extra example posted in this topic (returning 100 as the answer). I am quite sure that it reads the file correctly, as the original sum of the edges is computed as 261832, as verified to be correct in an earlier post here.

The (wrong) answer my program comes up with is a maximum saving of 208399. Does anyone maybe recognize from this answer what my mistake could be? I already tried typing it in three times today, so I'm positive it isn't just a typo or something

Edit: I've run my algorithm on the left 12x12 corner of the given matrix and it returns 17199. Can anyone verify whether this is correct?

[mpiotte]

...
Edit: I've run my algorithm on the left 12x12 corner of the given matrix and it returns 17199. Can anyone verify whether this is correct?

Correct for 12x12.

[thundre]

One way to check your algorithm is to count the number of edges that remain. It's very easy to calculate what the final edge count should be.

[Yfke]

Thanks thundre and mpiotte! I have finally been able to identify my problem. Something went wrong when two edges had the same weight, it's just bad luck that I didn't come across that when running my program on the example problems... ah well. Next stop: problem 108

[yourmaths]

Found the "bug." I was reading the question wrong. Very frustrating, but at least I have the answer now.

Indeed. Those of us getting the test answer of 93 are fundamentally misunderstanding the question being asked.