ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1266. Kirchhoff's Law

Why TLE on test #7? Anything wrong with my equation-solving?
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 25 Aug 2004 20:48
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);
{Calculate residence between every two nodes}
for k:=1 to m do begin
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.