Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Object Pascal: кроссплатформенные технологии > Задача не работает "Охрана"

Автор: Itiniti 26.4.2006, 18:55

условие:
Входной файл: роliсеХХ.in
Выходной файл: роliсеХХ.out
Дано N (1≤N≤100) пронумерованных объектов, которые охраняются и соединены К дорогами (1≤К≤4950). Из любого объекта в любой можно проехать дорогами. Движение каждой дорогой возможно в оба направления. Необходимо разместить подразделение охраны так, чтобы наиболее удаленный объект достигался как можно быстрее.
Постановка задачи:
Напишите программу, которая находит наилучшее место для подразделения охраны. Подразделение может находиться как на одном из объектов, так и на дороге между объектами. Имя исполняемого файла должно быть роliсеYY.ехе, где YY — номер участника.
Входной файл:
Имя входного текстового файла вводимого с клавиатуры должно быть роliсеХХ.in, где ХХ - номер теста. В первой строке, файл содержит натуральные числа N и К. В следующих К строках содержатся по три натуральных числа F, Т, S (объекты с номерами F и Т соединяет дорога длиной S километров, 1≤S≤100; непосредственно между F и Т может быть не более одной дороги).
Выходной файл:
Имя выходного текстового файла должно быть ро1iсеХХ.out, где ХХ - номер теста. Выходной файл должен содержать числа D, L, М, R (расстояние до наиболее удаленного пункта равно D, подразделение следует разместить в R километрах от объекта L на дороге до объекта М).
Пример:
Входной файл Выходной файл
3 2
1 2 1
1 3 2 1.5 1 3 0.5

Моё рещение:

Код


var n,a1,b1,x      : integer;
    k,i,l,j        : integer;
    a              : array[1..10,1..10] of integer;
    max1,max2,max3 : integer;
    s              : real;

procedure init;
begin
  fillchar(a,sizeof(a),0);
  assign(input,'police.dat');
  reset(input);
    readln(n,k);
    for i:=1 to k do begin
      readln(a1,b1,x);
      a[a1,b1]:=x;
      a[b1,a1]:=x;
    end;
  close(input);
end;

procedure solve;
begin
  for i:=1 to n do begin
    l:=0;
    for j:=1 to n do
      l:=l+a[i,j];
    a[i,n+1]:=l;
  end;
  max1:=0;
  for i:=1 to n do
    if a[i,n+1]>a[max1,n+1] then max1:=i;
  max2:=0;
  for i:=1 to n do
    if (a[i,n+1]>a[max2,n+1]) and (i<>max1) then max2:=i;
  max3:=0;
  for i:=1 to n do
    if (a[i,n+1]>a[max3,n+1]) and (i<>max2) and (i<>max1) then max3:=i;
  s:=(a[max1,n+1]+a[max3,n+1])/2;
end;

procedure print;
begin
  assign(output,'police.sol');
  rewrite(output);
    write(s+a[max3,n+1]:2:1,' ');
    if max1<max2 then write(max1,' ',max2,' ') else write(max2,' ',max1,' ');
    write(abs(s-a[max1,n+1]):2:1);
  close(output);
end;

begin
  init;
  solve;
  print;;
end.

Автор: comtat 3.5.2006, 21:55

это чета из теории расписания

вариация задачи о рюкзаке если не ошибаюсь