Задача
Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v1 и v2 и целое число C. Требуется:

  1. Определить, существует ли в заданном графе путь из вершины v1 в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам)

  2. Найти минимум функции |X - C|, где X - количество ребер в некотором пути из v1 в v2


Входные данные
Первая строка входного файла содержит целое число N - количество вершин в графе (1N10). В следующих N строках расположена матрица N×N из нулей и единиц, элемент (i,j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя.) Элементы матрицы во входном файле записаны без разделительных пробелов

Наконец, строка N+2 содержит номера вершин v1 и v2, а строка N+3 - десятичную запись числа C (1C<1050)

Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи: "Yes", если путь длины C существует, и "No" в противном случае. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v1 в v2 не существует, ваша программа должна вывести в выходной файл число "-1"


Например:

GRPATH.IN
3
010
001
100
1 1
555555555555555555555555555555555

GRPATH.OUT
Yes
0



Идеи
Зацикливание, динамическое программирование, графы, длинная арифметика.

Комментарии
Достаточно решить второй пункт задачи. Пусть Аi - множество вершин, в которые мы можем попасть из вершины vi, пройдясь по k ребрам. Будем последовательно вычислять множества A0, A1, A2 и т.д. Когда какое-то из этих множеств повторится, это означает, что рассматриваемая последовательность вошла в цикл (а это произойдет не позднее, чем через 2N 210 = 1024 шагов). Если число С достаточно большое, то с помощью деления определяем позицию цикла, которой оно соответствует. Далее находим ближайшее к этой позиции множество, содержащее v2. Здесь нужно внимательно разобрать возможные случаи, не забывая про существование предпериода


Упражнение
Решите ту же самую задачу методом динамического программирования при ограничении N50





Решение

{$A+,B-,D+,E-,F-,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} 
{$M 65520,0,655360} 
 
program grpath; 
const 
  nMax = 10; 
  maxPeriod = 1100; 
  maxLen = 1000; 
type 
  tPos = set of 1..10; 
  tNum = array[0..maxLen] of integer; 
var 
  a : array[1..nMax, 1..nMax] of boolean; 
  c, oldc : tNum; 
  n, v1, v2 : integer; 
  perL, predL : integer; 
  allPos : array[0..2*maxPeriod+1] of tPos; 
  min : integer; 
 
procedure init; 
var 
  s : string; 
  i, j : integer; 
begin 
  assign(input, 'grpath.in'); 
  reSet(input); 
  readLn(N); 
  for i := 1 to N do begin 
    readLn(s); 
    for j := 1 to N do 
      a[i, j] := s[j] = '1'; 
  end; 
 
  readLn(v1, v2); 
  readLn(s); 
  c[0] := length(s); 
  for i := 1 to c[0] do 
    c[i] := ord(s[c[0]-i+1])-ord('0'); 
  oldc := c; 
end; 
 
procedure getNext(var pos : tPos); 
var 
  i, j : integer; 
  next : tPos; 
begin 
  next := []; 
  for i := 1 to N do 
    if i in pos then 
      for j := 1 to N do 
        if a[i, j] then 
          include(next, j); 
   pos := next; 
end; 
 
procedure findPeriod; 
var 
  pos, next : tPos; 
  i : integer; 
begin 
  pos := [v1]; 
  allPos[1] := pos; 
  for i := 1 to 2*maxPeriod do begin 
    getNext(pos); 
    allPos[i+1] := pos; 
  end; 
 
  next := pos; getNext(next); 
  perL := 1; 
  while next <> pos do begin 
    getNext(next); 
    inc(perL); 
  end; 
 
  pos := [v1]; 
  next := [v1]; 
  for i := 1 to perL do 
    getNext(next); 
 
  predL := 0; 
  while next <> pos do begin 
    inc(predL); 
    getNext(next); 
    getNext(pos); 
  end; 
end; 
 
function toNum(const c : tNum) : longint; 
var 
  num, i : longint; 
begin 
  num := 0; 
  for i := c[0] downto 1 do 
    num := num*10+c[i]; 
 
  toNum := num; 
end; 
 
procedure dec(var a : tNum; n : integer); 
var 
  b : tNum; 
  r, i : integer; 
begin 
  fillChar(b, sizeOf(b), 0); 
  while n <> 0 do begin 
    inc(b[0]); 
    b[b[0]] := n mod 10; 
    n := n div 10; 
  end; 
 
  r := 1; 
  for i := 1 to a[0] do begin 
    r := a[i]-b[i]+9+r; 
    a[i] := r mod 10; 
    r := r div 10; 
  end; 
  while (a[0] > 0) and (a[a[0]] = 0) do 
    system.dec(a[0]); 
end; 
 
function Less(const c : tNum; num : integer) : boolean; 
var 
  a, i : longint; 
begin 
  if c[0] > 4 then 
    Less := false 
  else 
    Less := toNum(c) < num; 
end; 
 
function _mod(var c : tNum; k : integer) : integer; 
var 
  ans : longint; 
  i : integer; 
begin 
  ans := 0; 
  for i := c[c[0]] downto 1 do 
    ans := (ans*10+c[i]) mod k; 
 
  _mod := ans; 
end; 
 
procedure search(k, down, up : integer; cycle : boolean); 
var 
  i : integer; 
begin 
  min := maxInt; 
  i := k; 
  while (i >= down) and not (v2 in allPos[i]) do 
    system.dec(i); 
  if i >= down then begin 
    min := k-i; 
    if cycle and (min > perL-min) then 
      min := perL-min; 
  end; 
 
  i := k; 
  while (i <= up) and not (v2 in allPos[i]) do 
    inc(i); 
  if (i <= up) and (min > i-k) then begin 
    min := i-k; 
    if cycle and (min > perL-min) then 
      min := perL-min; 
  end; 
 
  if (min = maxInt) and cycle then begin 
    i := predL; 
    while (i > 0) and not (v2 in allPos[i]) do 
      system.dec(i); 
    if i > 0 then begin 
      min := -1; 
      dec(oldc, i-1); 
    end; 
  end; 
end; 
 
procedure print; 
var 
  i : integer; 
begin 
  assign(output, 'grpath.out'); 
  reWrite(output); 
 
  if min = 0 then 
    writeLn('Yes') 
  else 
    writeLn('No'); 
 
  if (min <> -1) and (min < maxInt) then 
    writeLn(min) 
  else 
    if min = -1 then begin 
      for i := c[0] downto 1 do 
        write(oldc[i]); 
      writeLn; 
    end 
    else 
      writeLn(-1); 
end; 
 
Begin 
  init; 
  findPeriod; 
  if Less(c, perL+predL) then 
    search(toNum(c)+1, 1, predL+perL, false) 
  else begin 
    dec(c, predL); 
    search(_mod(c, perL)+predL+1, predL+1, predL+perL, true); 
  end; 
 
  print; 
  close(input); close(output) 
End.

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