Описание
Задана электрическая схема из некоторого количества узлов и N резисторов, их соединяющих

Пояснения для тех, кто плохо учил в школе физику:

  1. Сила тока равна напряжению, поделенному на сопротивление: I=U/R

  2. Сумма токов, втекающих в узел, равна сумме токов, вытекающих из него

  3. Сумма падений напряжений I·R на отдельных участках произвольного замкнутого контура равна сумме всех ЭДС в этом контуре


Как следствие, получаем следующие формулы:

  1. При последовательном соединении резисторов с сопротивлениями R1 и R2 общее сопротивление R вычисляется по формуле R=R1+R2

  2. При параллельном соединении резисторов с сопротивлениями R1 и R2 общее сопротивление R вычисляется по формуле 1/R=1/R1+1/R2


Задание
Напишите программу, вычисляющую сопротивление между двумя заданными узлами A и B этой схемы. Допускается частичное решение задачи для случая параллельно-последовательных схем


Входные данные
В первой строке входного файла содержится целое число N – количество резисторов в схеме (1≤N≤50). Во второй строке записаны номера узлов A и B (узлы нумеруются начиная с 1). Каждая из следующих N строк содержит описание очередного резистора в виде тройки целых чисел из диапазона [0,32767], записанных через пробел. Первые два числа задают номера двух различных узлов схемы, которые этот резистор соединяет, а третье – его сопротивление. Между двумя узлами схемы могут располагаться несколько резисторов

Выходные данные
Выведите в выходной файл искомое сопротивление не менее чем с 6 верными значащими цифрами


Например:

RESIST.IN
4
1 2
1 3 1
3 4 1
4 3 1
2 4 1

RESIST.OUT
2.50




Комментарии
К заданному в условии задачи мультиграфу дополнительно добавим ребро от A к B, на котором располагается источник ЭДС. Для каждого ребра заведем неизвестную, равную току, протекающему по этому ребру в каком-то фиксированном направлении. Используем теперь алгоритм нахождения фундаментального множества циклов в графе [Липский 88, п.2.5]. Для каждого построенного цикла выпишем в виде уравнения на введенные неизвестные закон Кирхгофа для напряжений, указанный в условии задачи (ясно, что уравнения для всех остальных циклов будут линейными комбинациями выписанных). Кроме того, для каждого узла можно записать уравнение равенства сумм токов, втекающих и вытекающих из него. Такое уравнение нужно записать для всех узлов схемы, кроме любого одного (докажите, что уравнение для него равно сумме предыдущих с обратным знаком). Полученную систему из N+1 линейного уравнения с N+1 неизвестными решаем, например, методом Гаусса


Упражнения

  1. Докажите, что общее количество построенных уравнений (т.е. количество циклов в фундаментальном множестве циклов плюс количество узлов в схеме) равняется N+1

  2. Докажите, что полученная система линейных уравнений является невырожденной, т.е. будет иметь единственное решение
     

Решение

program resist;
 
{.$define DEBUG}
{$M 16384,102400,102400}
 
{$ifdef DEBUG}
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V-,X+,Y+}
const
  inFile  = 'resist.in';
  outFile = 'con';
{$else}
{$A+,B-,D+,E-,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X+,Y+}
const
  inFile  = 'resist.in';
  outFile = 'resist.out';
{$endif}
 
const
  maxN = 51;
  maxE = 51;
  eps  = 1e-8;
type
  float = extended;
  TEdge = record
    used : boolean;
    left, right : integer;
    r : float;
    helper : boolean;
  end;
  TVector = array[1..maxE] of float;
var
  nEdges : integer;
  edges : array[1..maxN] of TEdge;
  a, b : integer;
  nEq : integer;
  m : array[1..maxE] of TVector;
  w : TVector;
  answer : float;
 
procedure AppendEdge( _left, _right : integer; _r : float );
{_r < 0 denotes helper edge}
var
  tmp : integer;
 
begin
  if _left = _right then exit;
  if _left > _right then begin
    tmp := _left;
    _left := _right;
    _right := tmp;
  end;
  inc( nEdges );
  with edges[nEdges] do begin
    helper := _r < -eps;
    left   := _left;
    right  := _right;
    r      := _r;
    used   := false;
  end;
end;
 
procedure GaussElim;
var
  i, j, k : integer;
  max : float;
  tmp1 : TVector;
  tmp2 : float;
  coeff : float;
  v : integer;
 
begin
  v := 0;
  for i := 1 to nEq do begin
    max := 0;
    repeat
      inc( v );
      if v > nEdges then halt( 1 );
      for j := i to nEq do
        if abs( m[j,v] ) > max then begin
          k := j;
          max := abs( m[j,v] );
        end;
    until abs( max ) > eps;
 
    tmp1 := m[i];
    m[i] := m[k];
    m[k] := tmp1;
 
    tmp2 := w[i];
    w[i] := w[k];
    w[k] := tmp2;
 
    for j := i + 1 to nEq do begin
      coeff := m[j,v] / m[i,v];
      w[j] := w[j] - w[i] * coeff;
      for k := v to nEdges do
        m[j,k] := m[j,k] - m[i,k] * coeff;
    end;
 
  end;
  {$ifdef DEBUG}
  if abs( w[nEq] ) < eps then halt( 1 );
  {$endif}
  answer := abs( m[nEq,nEdges] / w[nEq] ) - 1;
end;
 
procedure BuildEqs;
var
  i, j : integer;
  f : boolean;
  visited : array[1..maxN*2] of boolean;
  from    : array[1..maxN*2] of integer;
  byEdge  : array[1..maxN*2] of integer;
 
  procedure ProcessCycle( i, j, iEdge : integer );
  var
    k, e : integer;
    oldFrom : integer;
 
  begin
    inc( nEq );
    for k := 1 to maxE do m[nEq,k] := 0;
    w[nEq] := 0;
 
    oldFrom := from[j];
    from[j] := i;
    byEdge[i] := iEdge;
 
    i := j;
    repeat
      k := from[i];
      e := byEdge[k];
      if edges[e].helper then begin
        if i = edges[e].left then begin
          m[nEq,e] := 1;
          w[nEq] := 1;
        end else begin
          m[nEq,e] := -1;
          w[nEq] := -1;
        end;
      end else begin
        if i < k then
          m[nEq,e] := edges[e].r
        else
          m[nEq,e] := -edges[e].r;
      end;
      i := k;
    until i = j;
    from[j] := oldFrom;
  end;
 
  procedure DFS( i : integer );
  var
    j, k : integer;
  begin
    visited[i] := true;
    for j := 1 to nEdges do
      if (edges[j].left = i) or (edges[j].right = i) then begin
        if edges[j].used then continue;
        edges[j].used := true;
        if edges[j].left = i then
          k := edges[j].right
        else
          k := edges[j].left;
 
        if visited[k] then begin
          ProcessCycle( i, k, j );
        end else begin
          from[k] := i;
          byEdge[i] := j;
          DFS( k );
        end;
      end;
  end;
 
begin
  AppendEdge( a, b, -1 ); {helper}
  fillchar( visited, sizeof(visited), false );
  fillchar( byEdge, sizeof(byEdge), 0 );
  from[a] := 0;
  nEq := 0;
  DFS( a );
 
  for i := 1 to nEdges * 2 do
    if visited[i] then begin
      inc( nEq );
      for j := 1 to nEdges do
        if (edges[j].left = i) or (edges[j].right = i) then begin
          if edges[j].left = i then
            m[nEq,j] := 1
          else
            m[nEq,j] := -1;
        end;
    end;
 
  dec( nEq ); {kill the last equation}
 
end;
 
procedure Solve;
begin
  if a = b then begin
    answer := 0;
    exit;
  end;
  BuildEqs;
  GaussElim;
end;
 
procedure ReadData;
var
  i, n : integer;
  x, y : integer;
  r : float;
 
begin
  read( n );
  read( a, b );
  for i := 1 to n do begin
    read( x, y, r );
    AppendEdge( x, y, r );
  end;
end;
 
procedure WriteData;
begin
  writeln( answer:0:10 );
end;
 
procedure Initialize;
begin
  assign( input, inFile );
  reset( input );
  assign( output, outFile );
  rewrite( output );
 
  {$ifdef DEBUG}
  writeln( '----Initialized----' );
  {$endif}
 
  nEdges := 0;
end;
 
procedure Finalize;
begin
  {$ifdef DEBUG}
  writeln( '----Finalized----' );
  {$endif}
  close( input );
  close( output );
end;
 
begin
  Initialize;
  ReadData;
  Solve;
  WriteData;
  Finalize;
end.

 

© Особенности национальных задач по информатике