Seems, programmers just know physics quite poorly)
This is just gauss. But don't forget about multiple edges.

Please add this test
4 3
1 3 1
3 2 1
2 4 1

what are the real restrictions for input data?

I just add in my source:

n = (n - 1) % 20 + 1, and have WA test 1;

else I have TL test 1.


then I send the code:


        scanf("%i%i", &n, &m);

    for (i = 0; i < m; i++)
    {
        scanf("%i%i%lf", &a, &b, &c);
        while (a > 10000 || b > 10000);
    }

    return 0;

and have TL test 1

Edited by author 28.04.2008 17:09

My solution used or than 8 Mb memory! So I couldn't pass this task until memory limit was increased :)

I make a system of size about 1000x1000 ( exactly M+N-2 ) of double. Then I slove it and have all currents and potential. After I select currents that start from the 1st point and R = 1/I.
How did you do this task using so less memory (<300Kb)?

P.S. What is the size of your source? Mine is 43 lines :)

If points there is no resistance between i and j that means that they are disconnected? Then if there is M = 0 the chain is disconnected! What did I misunderstand?

As I understand, there can be many edges (A,B) with R = 1000. That actually means, that the total R of (A,B) will be extremely big and that I will be very small. How should we deal with it?

Edited by author 31.05.2006 00:16

That made me get an ACCESS_VIOLATION!

Note:
1. e[i,j] stands for the coefficient of u[j] in the i'th equation, e[i,0] stands for the constant item of the i'th equation.
2. I swap the node numbers 1 and n-1.

-------Prog below-------
program ural1266;
const
  maxn=19;
  u0=1e9;
  zero=1e-6;
type
  equation=array[0..maxn-2]of real;
var
  r:array[1..maxn,1..maxn]of real;
  e:array[1..maxn-2]of equation;
  u:array[1..maxn-1]of real;
  n,i,j:byte;
  m,k:word;
  x:real;
  te:equation;
procedure convert(var x:byte);
  begin
    if x=1 then
      x:=n-1
    else if x=n-1 then
      x:=1;
  end;
begin
  assign(input,'1266.in');reset(input);
  read(n,m);
  {Calculate residence between every two nodes}
  for k:=1 to m do begin
    read(i,j,x);
    convert(i);convert(j);
    if r[i,j]=0 then r[i,j]:=x else r[i,j]:=r[i,j]*x/(r[i,j]+x);
    r[j,i]:=r[i,j];
  end;
  {Build equations}
  for i:=1 to n-2 do begin
    for j:=1 to n-2 do
      if r[i,j]>0 then begin
        e[i,i]:=e[i,i]+1/r[i,j];
        e[i,j]:=e[i,j]-1/r[i,j];
      end;
    if r[i,n-1]>0 then begin
      e[i,i]:=e[i,i]+1/r[i,n-1];
      e[i,0]:=e[i,0]+u0/r[i,n-1];
    end;
    if r[i,n]>0 then
      e[i,i]:=e[i,i]+1/r[i,n];
  end;
  {Solve equations}
  for i:=n-2 downto 2 do begin
    j:=i;
    while e[i,j]=0 do dec(j);
    if j<>i then begin
      te:=e[i];e[i]:=e[j];e[j]:=te;
    end;
    for j:=1 to i-1 do
      for k:=0 to i-1 do
        e[j,k]:=e[j,k]*e[i,i]-e[i,k]*e[j,i];
  end;
  for i:=1 to n-2 do begin
    for j:=1 to i-1 do
      e[i,0]:=e[i,0]-e[i,j]*u[j];
    u[i]:=e[i,0]/e[i,i];
  end;
  u[n-1]:=u0;
  {Calculate total current}
  x:=0;
  for i:=1 to n-1 do
    if r[i,n]>0 then x:=x+u[i]/r[i,n];
  writeln(u0/x:0:2);
end.