//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Thành phố trên sao hoả

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 16


Đề bài


Đầu thế kỷ 21, người ta thành lập một dự án xây dựng một thành phố trên sao Hoả để thế kỷ 22 con người có thể sống và sinh hoạt ở đó. Giả sử rằng trong thế kỷ 22, phương tiện giao thông chủ yếu sẽ là các phương tiện giao thông công cộng nên để đi lại giữa hai điểm bất kỳ trong thành phố người ta có thể yên tâm chọn đường đi ngắn nhất mà không sợ bị trễ giờ do kẹt xe. Khi mô hình thành phố được chuyển lên Internet, có rất nhiều ý kiến phàn nàn về tính hợp lý của nó, đặc biệt, tất cả các ý kiến đều cho rằng hệ thống đường phố như vậy là quá nhiều, làm tăng chi phí xây dựng cũng như bảo trì.

Hãy bỏ đi một số đường trong dự án xây dựng thành phố thoả mãn:

  • Nếu giữa hai địa điểm bất kỳ trong dự án ban đầu có ít nhất một đường đi thì sự sửa đổi này không làm ảnh hưởng tới độ dài đường đi ngắn nhất giữa hai địa điểm đó.
  • Tổng độ dài của những đường phố được giữ lại là ngắn nhất có thể

Dữ liệu: Vào từ file văn bản CITY.INP, chứa bản đồ dự án

  • Dòng thứ nhất ghi số địa điểm N và số đường phố m (giữa hai địa điểm bất kỳ có nhiều nhất là một đường phố nối chúng, n£200; 0£m£n*(n-1)/2)
  • m dòng tiếp theo, mỗi dòng ghi ba số nguyên dương u, v, c cho biết có đường hai chiều nối giữa hai địa điểm u, v và độ dài của con đường đó là c (c£10000)

Kết quả: Ghi ra file văn bản CITY.OUT, chứa kết quả sau khi sửa đổi

  • Dòng thứ nhất ghi hai số k,d. Trong đó k là số đường phố còn lại còn d là tổng độ dài của các con đường phố còn lại.
  • k dòng tiếp theo, mỗi dòng ghi hai số nguyên dương p, q cho biết cần phải giữ lại con đường nối địa điểm p với địa điểm q

Các số trên một dòng của các file CITY.INP, CITY.OUT được ghi cách nhau ít nhất một dấu cách

Ví dụ:

CITY.INP CITY.OUT
10 12

1 2 1

1 5 2

2 6 7

3 4 1

3 7 2

4 8 8

5 6 3

6 7 1

6 9 2

7 8 5

7 10 8

9 10 4

9 21

1 2

1 5

3 4

3 7

5 6

6 7

6 9

7 8

9 10


Hướng dẫn


[]


Chương trình


{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 16384,0,655360}

uses crt;

const
   tfi                  =       'CITY.INP';
   tfo                  =       'CITY.OUT';
   maxN                 =       200;
   Unseen               =       2000000;

type
   mangB                =       array[1..maxN] of byte;
   mangL                =       array[1..maxN] of LongInt;

var
   fi,fo                :       text;
   N,M                  :       LongInt;
   a                    :       array[1..maxN] of ^mangL;
   Gr                   :       array[1..maxN] of ^mangB;
   Tr                   :       array[1..maxN,1..maxN] of byte;
   S,D                  :       LongInt;


procedure CapPhat;
var i: integer;
begin
   for i:=1 to maxN do new(a[i]);
   for i:=1 to maxN do new(Gr[i]);
end;

procedure GiaiPhong;
var i: integer;
begin
   for i:=1 to maxN do Dispose(a[i]);
   for i:=1 to maxN do Dispose(Gr[i]);
end;



procedure Docdl;
var i,j,u,v,l: LongInt;
begin
   assign(fi,tfi); reset(fi);
   readln(fi,N,M);
   for i:=1 to N do
      for j:=1 to N do a[i]^[j]:=Unseen;
   for i:=1 to N do
      for j:=1 to N do Gr[i]^[j]:=0;
   for i:=1 to M do
      begin
         readln(fi,u,v,l);
         a[u]^[v]:=l; a[v]^[u]:=l;
         Gr[u]^[v]:=1; Gr[v]^[u]:=1;
      end;
   close(fi);
end;

procedure Floy;
var k,i,j: integer;
begin
   Fillchar(Tr,sizeof(Tr),0);
   for k:=1 to N do
      for i:=1 to N do
         for j:=1 to N do
            if a[i]^[j]>=a[i]^[k]+a[k]^[j] then
               begin
                  a[i]^[j]:=a[i]^[k]+a[k]^[j];
                  Tr[i,j]:=k;
               end;
end;

procedure Solve;
var i,j: LongInt;
begin
   for i:=1 to N do
      for j:=1 to N do
         if (Gr[i]^[j]=1) and (Tr[i,j]>0) then
            begin
               Gr[i]^[j]:=0;
               Gr[j]^[i]:=0;
            end;
   S:=0;
   D:=0;
   for i:=1 to N-1 do
      for j:=i+1 to N do
         if Gr[i]^[j]=1 then
            begin
               S:=S+a[i]^[j];
               D:=D+1;
            end;
end;

procedure inkq;
var i,j: LongInt;
begin
   assign(fo,tfo); rewrite(fo);
   writeln(fo,d,' ',S);
   for i:=1 to N-1 do
      for j:=i+1 to N do
         if Gr[i]^[j]=1 then
            writeln(fo,i,' ',j);
   close(fo);
end;

BEGIN
   CapPhat;
   Docdl;
   Floy;
   Solve;
   Inkq;
   GiaiPhong;
END.
Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 252,771 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: