02/10/2018, 14:40
KBUILD Spoj – Sửa cầu
Nguồn đề bài: http://vn.spoj.com/problems/KBUILD/ 1. Đề bài KBUILD Spoj Vì lo lắng Pirate sẽ buồn chán khi một thân một mình ở đảo hoang, bạn gái Pirate từ trong đất liền dự định sang chơi với anh ấy. Pirate đang sinh sống trên một quần đảo gồm N đảo. Vì các đảo khá gần nhau nên ...
Nguồn đề bài: http://vn.spoj.com/problems/KBUILD/
1. Đề bài KBUILD Spoj
Vì lo lắng Pirate sẽ buồn chán khi một thân một mình ở đảo hoang, bạn gái Pirate từ trong đất liền dự định sang chơi với anh ấy.
Pirate đang sinh sống trên một quần đảo gồm N đảo. Vì các đảo khá gần nhau nên chẳng cần thuyền bè gì, Pirate chỉ cần đốn đại cây dừa nào đó và bắc ngang là có thể đi được từ đảo này sang đảo khác. Vì không muốn hủy hoại môi trường nên anh ấy chỉ đốn N – 1 cây dừa làm cầu, vừa đủ để từ một đảo bất kì đi đến được hết mọi đảo còn lại.
Nhưng mà “Môi son, má đào, chân guốc cao gót làm sao em qua cầu dừa???”. Lo lắng sợ bạn gái sẽ rơi xuống biển và bị cá đuối nẫng mất, Pirate hộc tốc đi sửa chữa các cây cầu dừa. Anh đưa ra một lịch trình như sau: vào mỗi ngày sẽ đi kiểm tra mọi cây cầu trên đường đi từ đảo a đến đảo b.
Tuy nhiên, lịch trình đó khá là phi khoa học. Thực hiện, xong rồi, Pirate mới ngớ ra là không biết mình có bỏ sót cây cầu nào không?
Input
- Dòng thứ nhất: số nguyên N – số hòn đảo.
- N – 1 dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b – có một cây cầu dừa nối đảo a và đảo b.
- Dòng thứ N + 1: số nguyên M – số ngày kiểm tra.
- M dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b – ngày hôm đó, Pirate sẽ kiểm tra các cây cầu trên đoạn đường từ đảo a đến đảo b.
Output
- Một số nguyên duy nhất thể hiện số cây cầu chưa được kiểm tra.
Giới hạn
- 1 ≤ N, M ≤ 200000
- 60% số test có 1 ≤ N, M ≤ 5000
- 80% số test có 1 ≤ N, M ≤ 50000
Example
Input:
6
1 2
2 3
2 4
4 5
4 6
2
3 6
5 6
Output:
1
1 2 3 4 5 6 7 8 9 10 11 12 13 | Input: 6 1 2 2 3 2 4 4 5 4 6 2 3 6 5 6 Output: 1 |
Giải thích: Ngày thứ nhất, Pirate kiểm tra các cây cầu (2, 3), (2, 4) và (4, 6). Ngày thứ hai, anh kiểm tra các cây cầu (5, 4) và (4, 6). Cây cầu duy nhất chưa được kiểm tra là (1, 2).
2. Hướng dẫn Kbuild spoj
Tạo một đường trực tiếp từ đảo a, đến đảo b. Tìm cầu, số lượng cầu chính là đáp án.
3. Code tham khảo Kbuild spoj
const fi = 'KBUILD.inp';
fo = 'KBUILD.out';
type bangghi = record
u,v : longint;
end;
var
doc : array [1..1000000] of bangghi;
number, low, parent, deg: array [1..1000000] of longint;
head : array[0..1000000] of longint;
free : array[1..1000000] of longint;
free1 : array[1..1000000] of boolean;
adj : array [1..1000000] of longint;
iscut : array [1..1000000] of boolean;
n, m, count, dem1, dem2, dem : longint;
procedure readf;
var
u,v,i : longint;
begin
read (n);
for i := 1 to n - 1 do begin
read(u,v);
doc[i].u := u;
doc[i].v := v;
inc(deg[u]);
inc(deg[v]);
end;
read(m);
for i := n to n + m - 1 do
begin
read(u,v);
doc[i].u := u;
doc[i].v := v;
inc(deg[u]);
inc(deg[v]);
end;
head[1] := 1 ;
for i := 2 to n do
head[i] := head[i-1] + deg[i-1];
dem := 0;
for i := 1 to n - 1 + m do
begin
u := doc[i].u;
v := doc[i].v;
adj[head[u]] := v;
adj[head[v]] := u;
inc(dem);
free[head[u]] := dem;
free[head[v]] := dem;
inc(head[u]);
inc(head[v]);
end;
for i := 1 to n do
dec(head[i]);
end;
procedure visit (u : longint);
var
v,iv : longint;
begin
inc (count);
number[u] := count;
low[u] := n+1;
for iv := head[u - 1] + 1 to head[u] do
begin
v := adj[iv];
if free1[free[iv]] then
begin
free1[free[iv]] := false;
if parent[v] = 0 then
begin
parent[v] := u;
visit (v);
if low[u] > low[v] then low[u] := low[v];
end
else
if low[u] > number[v] then low[u] :=number[v];
end;
end;
end;
procedure solve;
var
u,v : longint;
begin
count := 0;
fillchar (parent,sizeof(parent),0);
fillchar(free1, sizeof(free1), true);
for u := 1 to n do
if parent[u] = 0 then begin
parent[u] := -1;
visit(u);
end;
end;
procedure process;
var
u,v,i : longint;
begin
for v := 1 to n do begin
u := parent[v];
if (u <> -1) and (low[v] >= number[v]) then inc(dem1);
end;
write(dem1);
end;
begin
// assign (input,fi); reset (input);
// assign (output,fo); rewrite (output);
readf;
solve;
process;
close (input);
close (output);
end.
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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 | const fi = 'KBUILD.inp'; fo = 'KBUILD.out'; type bangghi = record u,v : longint; end; var doc : array [1..1000000] of bangghi; number, low, parent, deg: array [1..1000000] of longint; head : array[0..1000000] of longint; free : array[1..1000000] of longint; free1 : array[1..1000000] of boolean; adj : array [1..1000000] of longint; iscut : array [1..1000000] of boolean; n, m, count, dem1, dem2, dem : longint; procedure readf; var u,v,i : longint; begin read (n); for i := 1 to n - 1 do begin read(u,v); doc[i].u := u; doc[i].v := v; inc(deg[u]); inc(deg[v]); end; read(m); for i := n to n + m - 1 do begin read(u,v); doc[i].u := u; doc[i].v := v; inc(deg[u]); inc(deg[v]); end; head[1] := 1 ; for i := 2 to n do head[i] := head[i-1] + deg[i-1]; dem := 0; for i := 1 to n - 1 + m do begin u := doc[i].u; v := doc[i].v; adj[head[u]] := v; adj[head[v]] := u; inc(dem); free[head[u]] := dem; free[head[v]] := dem; inc(head[u]); inc(head[v]); end; for i := 1 to n do dec(head[i]); end; procedure visit (u : longint); var v,iv : longint; begin inc (count); number[u] := count; low[u] := n+1; for iv := head[u - 1] + 1 to head[u] do begin v := adj[iv]; if free1[free[iv]] then begin free1[free[iv]] := false; if parent[v] = 0 then begin parent[v] := u; visit (v); if low[u] > low[v] then low[u] := low[v]; end else if low[u] > number[v] then low[u] :=number[v]; end; end; end; procedure solve; var u,v : longint; begin count := 0; fillchar (parent,sizeof(parent),0); fillchar(free1, sizeof(free1), true); for u := 1 to n do if parent[u] = 0 then begin parent[u] := -1; visit(u); end; end; procedure process; var u,v,i : longint; begin for v := 1 to n do begin u := parent[v]; if (u <> -1) and (low[v] >= number[v]) then inc(dem1); end; write(dem1); end; begin // assign (input,fi); reset (input); // assign (output,fo); rewrite (output); readf; solve; process; close (input); close (output); end. |
