Destination Goa wrote:What's the reason of O((m+n)^2) = O(n^4) solution if basic approach works at O(n^3)?

O((m+n)^2) =?= O(n^4) ?? I don't think so
Actually the method Christian describes is O((n+m)^3).

Destination Goa wrote:Joey,
If you set x as potential in some cell, then parallel resistors are eliminated automatically during building matrix A (otherwise you'll get WA).

Yes, but you build an entirely different matrix by this approach, and no resistors are eliminated automaticly.

What is m? Number of resistors? If so, then m = O(n^2).

About auto-elimination. Do you mean eliminating resistors connecting same pair nodes or something else? I think we talk about different solutions here.

Mine is: let x[1]...x[N] be potentials of N nodes. c[1]...c[N] is current excess (0 for all, except +1 for source and -1 for destination). Equation system is X*A=C.

Initially A is all zeroes. Then, for each resistor R connecting V1;V2

a[v1][v2] += 1/r;
a[v1][v1] -= 1/r;

a[v2][v1] += 1/r;
a[v2][v2] -= 1/r;

So, this is O(m+n^3) solution (n - number of nodes, m - number of resistors), and it sums duplicate resistors automatically. Actually, it stores sum(1/R1+1/R2+...+1/Rk) for each pair (v1;v2) where resistors R1...Rk connect this pair in either direction.

Destination Goa wrote:What is m? Number of resistors? If so, then m = O(n^2).

Aha. Ok I see it, sorry.

Destination Goa wrote:About auto-elimination. Do you mean eliminating resistors connecting same pair nodes or something else? I think we talk about different solutions here.

That was were I was talking about. The method Christian describes (and which I implemented) _is_ completely different from the method you describe. And the things I descibed were applying to this other method, not yours.

It's merely a complete graph of 6 nodes with arbitary values on all edges. So I want ask whether other solver (with long long) can produce correct output for this case. Is it my luck to get AC?