Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCACM11E/
Nội dung bài viết
1. Đề bài BCACM11E spoj PTIT
Một hệ thống phòng thủ của địch gồm N điểm (N<=100), giữa các điểm bất kỳ của hệ thống đều có thể đi lại trực tiếp hoặc gián tiếp với nhau thông qua hệ thống các đường hầm. Bài toán được đặt ra là cho trước một hệ thống phòng thủ, hãy giúp bộ đội sử dụng đúng 1 quả pháo bắn vào một trong N điểm sao cho hệ thống bị chia cắt thành nhiều mảnh nhất.
Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test được tổ chức theo khuôn dạng sau:
- Dòng đầu tiên ghi lại số tự nhiên N không lớn hơn 100 là số điểm của hệ thống phòng thủ.
- Những dòng kế tiếp ghi lại ma trận G = (gij) biểu diễn hệ thống phòng thủ, trong đó gij=0 được hiểu là không có đường hầm trực tiếp nối giữa điểm i và j, gij =1 được hiểu có đường hầm nối trực tiếp giữa điểm i và điểm j (1<=i, j<=N).
Output: Với mỗi bộ test, in ra màn hình trên một dòng một số duy nhất là đỉnh bị phá hủy thỏa mãn yêu cầu bài toán (nếu có nhiều đỉnh cùng thỏa mãn yêu cầu thì in ra đỉnh có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống, hãy in ra số 0.
Example
Input:
2
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
5
0 1 1 0 0
1 0 1 0 1
1 1 0 1 1
0 0 1 0 1
0 1 1 1 0
Output:
3
0
2. Hướng dẫn BCACM11E spoj PTIT
– Đưa bài toán về mô hình đồ thị sử dụng thuật toán “Khớp” đếm số thành phần liên thông khi bỏ đỉnh i nào đó khỏi đồ thị.
– Thực hiện duyệt tất cả các đỉnh 1->n, đồng thời lưu khớp có nhiều thành phần liên thông nhất.
3. code tham khảo BCACM11E spoj PTIT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | const fi=''; nmax=100; type data=longint; matran=array[0..nmax+1,0..nmax+1] of byte; var f:text; A,B:matran; n,test:data; dd:array[1..nmax] of boolean; procedure init; var i:data; begin for i:=1 to n do dd[i]:=false; end; procedure dfs(i:data); var j:data; begin dd[i]:=true; for j:=1 to n do if (not dd[j]) and (b[i,j]=1) then dfs(j); end; function SPT:data; var i,sl:data; begin sl:=0; init; for i:=1 to n do if not dd[i] then begin inc(sl); dfs(i); end; exit(sl); end; function khop(i:data):data; var j,stplt:data; begin stplt:=spt; for j:=1 to n do begin B[i,j]:=0; B[j,i]:=0; end; khop:=spt; if not (khop>stplt+1) then khop:=0; b:=a; end; procedure xuli; var i,j,dinh,max,tmp:data; begin B:=A; dinh:=1; max:=khop(1); for i:=2 to n do begin tmp:=khop(i); if tmp>max then begin max:=tmp; dinh:=i; end; end; if max=0 then writeln(0) else writeln(dinh); end; procedure docfile; var i,j,x:data; begin assign(f,fi); reset(f); readln(f,test); for x:=1 to test do begin readln(f,n); for i:=1 to n do begin for j:=1 to n do read(f,a[i,j]); readln(f); end; xuli; end; end; begin docfile; end. |
Bài viết liên quan
- BCGRASS spoj PTIT – Bãi cỏ ngon nhất
- BCISLAND PTIT spoj – Nước biển
- C11BC2 spoj – Robin
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- VDANGER SPOJ- Nguy hiểm rõ ràng trước mắt
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- BCLKCOUN spoj PTIT – Đếm số ao
- BCBIN spoj PTIT – Các thùng nước
- BCACM11D spoj PTIT – Đường nguyên tố