Nguồn đề bài: http://vn.spoj.com/problems/REFORM/
1. Đề bài REFORM spoj
Mạng giao thông của thành phố NВ có n nút giao thông và m đoạn đường phố hai chiều nối các nút giao thông. Các nút giao thông được đánh số từ 1 đến n. Các đoạn đường phố được đánh số từ 1 đến m. Mạng giao thông của thành phố có tính chất sau đây:
- Giữa hai nút giao thông bất kỳ có không quá một đoạn đường phố nối chúng;
- Không có đoạn đường phố nào nối một nút giao thông với chính nó.
Vấn đề giao thông là thách thức với chính quyền thành phố từ nhiều năm. Với mong muốn đảm bảo việc đi lại thuận lợi hơn cho người dân, chính quyền thành phố quyết định tiến hành cải tổ mạng giao thông, trước hết nhằm đảm bảo có thể đi từ một nút giao thông bất kỳ đến tất cả các nút còn lại. (Lưu ý là mạng giao thông trước khi cải tổ có thể không đảm bảo yêu cầu này.) Tuy nhiên, do hạn hẹp về nguồn kinh phí, trước mắt kế hoạch cải tổ chỉ có thể bao gồm 2 công việc:
- Loại bỏ một đoạn đường phố hiện có khỏi mạng giao thông;
- Xây dựng một đoạn đường chưa từng có trước đó nối hai nút giao thông khác nhau.
Đồng thời, sau khi thực hiện cải tổ, mạng giao thông phải đảm bảo có thể đi từ một nút giao thông bất kỳ đến tất cả các nút còn lại.
Yêu cầu
Giúp chính quyền thành phố xác định xem có bao nhiêu cách khác nhau để thực hiện kế hoạch cải tổ thỏa mãn các yêu cầu đặt ra. (Hai kế hoạch cải tổ là khác nhau nếu có ít nhất một trong hai đoạn đường được lựa chọn loại bỏ hay xây dựng mới là khác nhau.)
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên n và m;
- Dòng thứ i trong số m dòng tiếp theo chứa hai số nguyên ui và vi (1 ≤ ui, vi ≤ n, ui≠ vi) là chỉ số của hai nút giao thông được nối bởi đoạn đường i (i = 1, 2, …, m).
Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.
Dữ liệu ra
- Ghi ra một số nguyên là số cách thực hiện kế hoạch cải tổ mạng giao thông thỏa mãn các yêu cầu đặt ra.
Ví dụ
Test 1:
input 4 4 1 2 2 3 2 4 3 4 output 8
Hình vẽ minh họa:
Test 2:
inout 7 5 1 2 3 4 5 6 5 7 6 7 output 0
Hình vẽ minh họa:
Ràng buộc
30% số test có 1≤n≤20.
70% số test còn lại có 1≤n≤100000, 0≤m≤200000.
2. Lời giải REFORM spoj
-Bài toán được phát biểu trên mô hình đồ thị:
Cho đồ thị vô hướng n đỉnh và m cạnh. Đếm số cách khác nhau đề thực hiên 2 công việc:
- Loại bỏ 1 cạnh trong m cạnh của đồ thị.
- Thêm cạnh mới vào đồ thị (cạnh này phải khác m cạnh lúc đầu) sao cho đồ thị mới đảm bảo tính liên thông.
-Nhận xét: ta chỉ có thể thêm 1 cạnh vào đồ thị nên số thành phần liên thông tối đa chỉ là 2. Ta chia bài toán thành 2 trường hợp:
- Đồ thị gồm 2 thành phần liên thông
-Giả sử 2 thành phần liên thông của đồ thị có số đỉnh lần lượt là C1 và C2 (C1+C2=n). Do đồ thị có 2 thành phần liên thông, ta cần 1 cạnh nối 2 thành phần liên thông này với nhau và số cách nối là C1*C2. Đối với cạnh cần bỏ đi, ta có một nhận xét là cạnh này không được là cầu (bởi nếu bỏ đi cầu, số thành phần liên thông sẽ tăng lên). Do đó, số cách tính được trong trường hợp này là (m-c)*C1*C2 (với c là số cầu của đồ thị). - Đồ thị chỉ có 1 thành phần liên thông
-Xét cạnh bị bỏ đi, ta có 2 trường hợp:
a. Cạnh bỏ đi không là cầu: đồ thị vẫn liên thông sau khi bỏ cạnh. Do đó, ta có thể thêm bất kì cạnh nào khác m cạnh lúc đầu. Ta có n*(n-1)/2-m cách thêm cạnh mới.
b. Cạnh bỏ đi là cầu: đồ thị sẽ bị chia thành 2 thành phần liên thông. Do đó, cạnh thêm vào phải nối 2 thành phần liên thông đó lại. Gọi C1 và C2 lần lượt là số đỉnh của 2 thành phần liên thông đó. Ta có C1*C2-1 cách thêm (không tính cạnh vừa bỏ đi).
- Đồ thị gồm 2 thành phần liên thông
-Cuối củng chỉ việc tính tổng số cách trong từng trường hợp.
⇒ Độ phức tạp O(m+n).
3. Code REFORM spoj
a. Code c++
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define REP(i,a,b) for(int i=a; i>=b; i--)
#define ll long long
#define pb push_back
#define getbit(x, pos) ((x >> (pos - 1)) & 1)
#define sz(x) (int)x.size()
const int Nmax = 100100;
vector<int> ad[Nmax];
int n, m, c1 = 0, cnt = 0, num[Nmax], low[Nmax], child[Nmax], root,
Count, bridge;
bool Free[Nmax];
// DFS để đếm thành phần liên thông cũng như tìm các cầu.
void visit(int p, int i) {
if (Count == 1) c1++;
num[i] = ++cnt;
low[i] = num[i];
child[i] = 1;
Free[i] = 1;
FOR(j, 0, sz(ad[i]) - 1) if (ad[i][j] != p) {
if (Free[ad[i][j]] == 0) {
visit(i, ad[i][j]);
child[i] += child[ad[i][j]];
low[i] = min(low[i], low[ad[i][j]]);
} else low[i] = min(low[i], num[ad[i][j]]);
}
if (root != i && low[i] == num[i]) bridge++;
}
int main() {
cin >> n >> m;
FOR(i, 1, m) {
int x, y;
cin >> x >> y;
ad[x].pb(y);
ad[y].pb(x);
}
Count = 0;
memset(Free, 0, sizeof Free);
FOR(i, 1, n) if (Free[i] == 0) {
root = i;
Count++;
visit(0, i);
}
// trường hợp đồ thị có >= 3 thành phần liên thông, kết quả là 0
if (Count >= 3) {
cout << 0;
return 0;
}
ll res;
if (Count == 2) {
// trường hợp đầu tiên.
res = (ll)(m - bridge) * c1 * (n - c1);
} else {
res = (ll)(m - bridge) * ((ll)n * (n - 1)/2 - m);
// cố định cầu bằng cách cố đỉnh các đỉnh từ 2 tới n và cha của các đỉnh tương ứng.
// low[i] == num[i] nghĩa là i - cha[i] là cầu
FOR(i, 2, n) if (low[i] == num[i])
res += (ll)child[i] * (n - child[i]) - 1;
}
cout << res;
return 0;
}b. code pascal
const fi='';
nmax=1000000;
mmax=400000;
type data=longint;
var
f:text;
adj,x,y:array[0..mmax+1] of data;
head:array[0..nmax+1] of data;
sl:array[0..nmax+1] of int64;
low,num,tr:array[0..nmax+1] of data;
n,m,dinh,lab,sl1,res,khop,cau:int64;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
read(f,n,m);
for i:=0 to n+1 do
head[i]:=0;
for i:=1 to m do
begin
read(f,x[i],y[i]);
inc(head[x[i]]);
inc(head[y[i]]);
end;
for i:=1 to n+1 do
head[i]:=head[i-1]+head[i];
for i:=1 to m do
begin
adj[head[x[i]]]:=y[i];
dec(head[x[i]]);
adj[head[y[i]]]:=x[i];
dec(head[y[i]]);
end;
close(f);
end;
function min(a,b:data):data;
begin
if a<b then exit(a); exit(b);
end;
procedure dfs(u:data);
var v,k,i:data;
s:boolean;
begin
inc(lab);
low[u]:=lab;
num[u]:=lab;
k:=0;
sl[u]:=1;
s:=false;
for v:=head[u]+1 to head[u+1] do
if tr[u]<>adj[v] then
begin
if num[adj[v]]=0 then
begin
tr[adj[v]]:=u;
inc(k);
dfs(adj[v]);
if low[adj[v]]>=num[u] then
s:=true;
sl[u]:=sl[adj[v]]+sl[u];
low[u]:=min(low[u],low[adj[v]]);
end
else
low[u]:=min(low[u],num[adj[v]]);
end;
if ((s and (tr[u]<>0)) or ((tr[u]=0) and (k>1))) then inc(khop);
if (Low[u]=num[u]) and (tr[u]<>0) then inc(cau);
end;
procedure ddfs(u:data);
var
v:data;
begin
inc(dinh);
num[u]:=1;
for v:=head[u]+1 to head[u+1] do
if num[adj[v]]=0 then
ddfs(adj[v]);
end;
procedure xuli;
var i,j:data;
stplt:int64;
begin
for i:=1 to n do
num[i]:=0;
stplt:=0;
sl1:=0;
for i:=1 to n do
if num[i]=0 then
begin
dinh:=0;
ddfs(i);
if sl1=0 then
sl1:=dinh;
inc(stplt);
end;
if stplt>2 then
begin
writeln('0');
exit;
end;
for i:=1 to n do
num[i]:=0;
tr:=num;
cau:=0;
khop:=0;
lab:=0;
for i:=1 to n do
if num[i]=0 then
dfs(i);
if stplt=1 then
begin
res:=(m-cau)*((n*(n-1)) div 2 - m);
for i:=2 to n do
if low[i]=num[i] then
res:=res+int64(sl[i])*(int64(n-sl[i]))-1;
writeln(res);
exit;
end;
if stplt=2 then
begin
res:=(m-cau)*sl1*(n-sl1);
writeln(res);
end;
end;
begin
docfile;
xuli;
end.
