Giúp với đề thi HSG nghệ an 2007-2008

Bài 1 (7 điểm)
ĐƯỜNG HẦM
Có N hòn đảo đánh số từ 1 đến N. Một số hòn đảo đã có đường hầm thông với nhau.
Người ta muốn xây dựng thếm một số đường hầm sao cho có thể đi lại giữa 2 hòn đảo bất kỳ
bằng đường hầm. Biết rằng đường hầm nối các đảo là đường đi 2 chiều, hãy lập trình tính số
đường hầm ít nhất cần xây dựng thên.
Dữ liệu: vào từ file văn bản HAM.INP gồm
- Dòng đầu tiên la số N(1<=N<=100).
-Các dòn tiếp theo mỗi dòng ghi hai số i và j cho biết có đường hầm nối giữa 2 hòn đảo u va j.
Kết quả :ghi ra file văn bản HAM.OUT chỉ số suy nhất cho biết số đường hầm ít nhất cần xây dựng
thêm.
Ví dụ


HAM.INP
HAM.OUT
92
1 3
1 5
1 6
2 7
4 8
8 9
 
  • Chủ đề
    de thi hsg tinhoc
    • T

    tengiday

    Happy life
    Reply: giúp với đề thi HSG nghệ an 2007-2008

    Bạn xây dựng đồ thị với đỉnh là hòn đảo đc đánh số từ 1 tới N; 2 đỉnh u và v đc nối với nhau nếu có đg` hầm nối 2 hòn đảo. Đây là đồ thị vô hướng vì đg` hầm là 2 chiều. Sau đó, bạn duyệt đồ thị (dùng BFS hay DFS đều đc), tìm số lượng connected components của đồ thị. Số đg` hầm cần thêm vào chính là số connected components trừ đi 1.
     
    T

    tengiday

    Happy life
    Bài này thuộc về graph theory rồi, không thích hợp nếu bạn mới học lập trình đâu. Mình không thể viết toàn bộ lý thuyết đồ thị cơ bản lên đây đc chỉ có thể nói gọn thôi. Cách làm bài này là:
    1) Xây dựng đồ thị:
    - Dùng 1 mảng 2 chiều n x n để đánh dấu. a[i, j] = 1 nếu đã có đg` hầm từ đảo i tới đảo j (và a[j, i] = 1 vì đg` hầm là 2 chiều). Còn lại a[i, j] = 0.
    - Mình ghi code đơn giản như bên dưới để xây dựng đồ thị như trong ví dụ:
    [ah]
    Mã: 
    procedure read_data;
var i, j : integer;
begin
    n := 9;
    for i := 1 to n do
        for j := 1 to n do
            a[i, j] := '0';
    a[1, 3] := '1'; a[3, 1] := '1';
    a[1, 5] := '1'; a[5, 1] := '1';
    a[1, 6] := '1'; a[6, 1] := '1';
    a[2, 7] := '1'; a[7, 2] := '1';
    a[4, 8] := '1'; a[8, 4] := '1';
    a[8, 9] := '1'; a[9, 8] := '1';
end;
    [/ah]
    Bạn cần đọc file và sửa lại a[i, j] = '1' tùy theo nhé.

    2) Xử lý:
    - Từ mỗi hòn đảo, đi theo các cung "đường hầm" để xem đến đc những đảo nào. Đảo nào đến đc thì đánh dấu lại và không đi trùng. Có 2 thuật toán cơ bản để duyệt là DFS (depth first search) và BFS (breadth first search). Trong code mình dùng DFS vì dễ viết. Nếu từ 1 hòn đảo có thể đi đc đến những hòn đảo nào khác thì nguyên cụm đó gọi là "connected component" của đồ thị (thành phần liên thông).
    - Bởi vì không cần xây dựng đg` hầm với những đảo nằm trong một thành phần liên thông nữa, nên chúng ta chỉ quan tâm tới giữa những thành phần liên thông với nhau. Ví dụ nếu có M điểm thì phải cần M - 1 đoạn thẳng nối nó lại. Như vậy, số đg` hầm chính là số thành phần liên thông trừ đi cho 1.
    [ah]
    Mã: 
    procedure dfs(start : integer);
var i : integer;
begin
    color[start] := 'g';
    for i := 1 to n do
        if (color[i] = 'w') and (a[start, i] = '1') then
            dfs(i);
end;

function number_of_tunnels() : integer;
var i, count : integer;
begin
    // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
    for i := 1 to n do
        color[i] := 'w';
    // đếm thành phần liên thông
    count := 0;
    for i := 1 to n do
        if (color[i] = 'w') then
            begin
                dfs(i);
                count := count + 1;
            end;
    exit(count - 1);
end;
    [/ah]
    Biến khai báo là:
    [ah]
    Mã: 
    const MAXN = 100;
var a : array[1..MAXN, 1..MAXN] of char;
    color : array[1..MAXN] of char;
    n : integer;
    [/ah]
    Bạn xem visualization về cách duyệt DFS trong link sau (chọn Undirected Graph), nhập vào đỉnh bắt đầu duyệt rồi nhấn "Run DFS": Bạn kéo slider bên dưới để giảm tốc độ lại khi xem.
    HTML: 
    https://www.cs.usfca.edu/~galles/visualization/DFS.html
     
    H

    hoangtungok123

    cảm ơn cậu nhiều nha! tớ mới học đc mấy tháng thui!!.
    nên mấy bài này hơi trìu tượng. tớ vẫn chưa hiểu rõ lắm c giải thích rõ hơn đc ko?
     
    T

    tengiday

    Happy life
    hoangtungok123:
    cảm ơn cậu nhiều nha! tớ mới học đc mấy tháng thui!!.
    nên mấy bài này hơi trìu tượng. tớ vẫn chưa hiểu rõ lắm c giải thích rõ hơn đc ko?
    Nhấn để mở rộng...
    Bạn không rõ ở bước nào? Phần xây dựng đồ thị hay là phần xử lý chính? Đây là hình vẽ của ví dụ trong đề bài, mỗi một hòn đảo tượng trưng cho hình tròn đc đánh số từ 1 tới 9. Hai vòng tròn nối với nhau nếu có đg` hầm đi qua giữa 2 đảo. Nhìn vào hình bạn thấy rất rõ có 3 thành phần liên thông:
    Mã: 
     {1, 3, 5, 6}, {2, 7}, {4, 8, 9}
    Rõ ràng, trong cùng 1 thành phần liên thông thì có thể tự do qua lại thoải mái giữa các đảo, và ta cần xây thêm nhiều nhất là 1 đg` hầm để đi sang thành phần liên thông khác. Như vậy có tổng cộng là 2 đg` hầm.
    fpCtPW.png

    Mảng 2 chiều tương ứng với hình vẽ trên là
    Mã: 
       [B]1  2  3  4  5  6  7  8  9[/B]
[B]1[/B]  0  0  1  0  1  1  0  0  0
[B]2[/B]  0  0  0  0  0  0  1  0  0
[B]3[/B]  1  0  0  0  0  0  0  0  0
[B]4  [/B]0  0  0  0  0  0  0  1  0
[B]5  [/B]1  0  0  0  0  0  0  0  0
[B]6  [/B]1  0  0  0  0  0  0  0  0
[B]7  [/B]0  1  0  0  0  0  0  0  0
[B]8  [/B]0  0  0  1  0  0  0  0  1
[B]9  [/B]0  0  0  0  0  0  0  1  0
     
    H

    hoangtungok123

    bạn viết chương trinh đầy đủ dc ko?
    procedure dfs(start : integer);
    var i : integer;
    begin
    color[start] := 'g'; {chỗ này t ko hiểu sao lại là 'g'}
    for i := 1 to n do
    if (color = 'w') and (a[start, i] = '1') then {cả 'w' nữa}
    dfs(i);
    end;

    function number_of_tunnels() : integer;
    var i, count : integer;
    begin
    // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
    for i := 1 to n do
    color := 'w';
    // đếm thành phần liên thông
    count := 0;
    for i := 1 to n do
    if (color = 'w') then
    begin
    dfs(i);
    count := count + 1;
    end;
    exit(count - 1);{ý nghĩa câu này là gì ? }
    end;
     
    T

    tengiday

    Happy life
    - Mình viết cho bạn đã 90% chương trình rồi. Bạn chỉ còn viết phần đọc file lấy từng cặp số i, j rồi gán a[i, j] = '1' và a[j, i] = '1'. Sau đó, gộp nó lại với phần xử lý là chạy được thôi.
    - Mảng 'color' dùng để đánh dấu đỉnh chưa đến ('w' = white, chưa đến), hay đến rồi ('g' = grey = đến rồi). Bạn dùng cặp character nào cũng được cả. Mình sử dụng nó là thói quen rồi, có thể '0' và '1' nữa.
    - exit(....) là để function trả ra giá trị đó ngay lập tức mà không chạy tiếp nữa.
     
    H

    hoangtungok123

    ông viết cho rui code hoàn chỉnh đi giúp tui với. mai nộp rùi nhé làm ơn!
    tui đọc ko hiểu gì ý
     
    T

    tengiday

    Happy life
    Mình không dùng Pascal đã lâu rồi, nhất là khoảng nhập xuất file, nên chưa test kỹ:
    Mã: 
    const MAXN = 100;
      FI = 'HAM.INP';
      FO = 'HAM.OUT';
var a : array[1..MAXN, 1..MAXN] of char;
    color : array[1..MAXN] of char;
    n : integer;
    
procedure dfs(start : integer);
var i : integer;
begin
    color[start] := 'g';
    for i := 1 to n do
        if (color[i] = 'w') and (a[start, i] = '1') then
            dfs(i);
end;

function number_of_tunnels() : integer;
var i, count : integer;
begin
    // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
    for i := 1 to n do
        color[i] := 'w';
    // đếm thành phần liên thông
    count := 0;
    for i := 1 to n do
        if (color[i] = 'w') then
            begin
                dfs(i);
                count := count + 1;
            end;
    exit(count - 1);
end;

procedure read_data;
var f : text;
    i, j : integer;
begin
    assign(f, FI);
    reset(f);
    readln(f, n);
    for i := 1 to n do
        for j := i to n do
            begin
                a[i, j] := '0';
                a[j, i] := '0';
            end;
    while not eof do
        begin
            readln(f, i, j);
            a[i, j] := '1';
            a[j, i] := '1';
        end;
    close(f);
end;

procedure write_data(k : integer);
var f : text;
begin
    assign(f, FO);
    rewrite(f);
    writeln(f, k);
    close(f);
end;

BEGIN
    read_data;
    write_data(number_of_tunnels());
END.
     
    H

    hoangtungok123

    tengiday:
    Mình không dùng Pascal đã lâu rồi, nhất là khoảng nhập xuất file, nên chưa test kỹ:
    Mã: 
    const MAXN = 100;
      FI = 'HAM.INP';
      FO = 'HAM.OUT';
var a : array[1..MAXN, 1..MAXN] of char;
    color : array[1..MAXN] of char;
    n : integer;
    
procedure dfs(start : integer);
var i : integer;
begin
    color[start] := 'g';
    for i := 1 to n do
        if (color[i] = 'w') and (a[start, i] = '1') then
            dfs(i);
end;

function number_of_tunnels() : integer;
var i, count : integer;
begin
    // mảng dấu để đánh dấu những đỉnh đã đến rồi. Khởi tạo ban đầu là chưa đến đỉnh nào cả.
    for i := 1 to n do
        color[i] := 'w';
    // đếm thành phần liên thông
    count := 0;
    for i := 1 to n do
        if (color[i] = 'w') then
            begin
                dfs(i);
                count := count + 1;
            end;
    exit(count - 1);
end;

procedure read_data;
var f : text;
    i, j : integer;
begin
    assign(f, FI);
    reset(f);
    readln(f, n);
    for i := 1 to n do
        for j := i to n do
            begin
                a[i, j] := '0';
                a[j, i] := '0';
            end;
    while not eof do
        begin
            readln(f, i, j);
            a[i, j] := '1';
            a[j, i] := '1';
        end;
    close(f);
end;

procedure write_data(k : integer);
var f : text;
begin
    assign(f, FO);
    rewrite(f);
    writeln(f, k);
    close(f);
end;

BEGIN
    read_data;
    write_data(number_of_tunnels());
END.
    Nhấn để mở rộng...
    tớ chạy nó lỗi cậu xem lại hộ tớ đi !!
     
    T

    tengiday

    Happy life
    hoangtungok123:
    tớ chạy nó lỗi cậu xem lại hộ tớ đi !!
    Nhấn để mở rộng...
    Bạn cho mình biết thông báo lỗi mới fix đc. Bạn kiểm tra lại xem mảng 'a' đã nhập chính xác hay chưa. Nếu lỗi nhập xuất file thì bạn có thể tự sửa đc. Mình không có Pascal nên chỉ có thể dùng online Pascal mà thôi, bởi vậy mình không làm phần đọc xuất file bao giờ cả.
     
    Đăng nhập bằng tài khoản VFO hoặc Google

    Bài viết mới nhất

    Thống kê

    Chủ đề
    100,657
    Bài viết
    467,424
    Thành viên
    339,831
    Thành viên mới nhất
    TuanShinhanbank

    Bài viết được quan tâm nhiều

    Top