ADS – spoj

Đề bài:

• http://vn.spoj.com/problems/ADS/

Thuật toán:

• Kết quả là: m – n + số thành phần liên thông
• Chứng minh
  1. Nếu 1 thành phần liên thông thì cách xếp hành trình tối ưu nhất là xếp hành trình của mỗi nhân viên có một con đường riêng còn lại giống nhau (“Hành trình phân công cho mỗi nhân viên phải có ít nhất một đoạn đường chưa có nhân viên nào khác đi tiếp thị.”) Giả sử có 1 cây khung n-1 cạnh =>  còn lại m-n+1 cạnh thừa => xếp nhiều nhất thêm m-n+1 hành trình.
  2. Nếu có nhiều thành phần liên thông thì tương tự. Kết quả là: SUM(m[i]-n[i]+1) = m – n +1 với i=1..n, m[i] là số cạnh tplt i, n[i] số đỉnh tplt i.

Code:

• Pascal (xem)

const   fi='';
        fo='';
        maxn=2000;
var     a:array[1..maxn,1..maxn] of boolean;
        cx:array[1..maxn] of boolean;
        i,j,n,m,res,x,y,dem:integer;
procedure dfs(u:integer);
var     v:integer;
begin
    cx[u]:=true;
    for v:=1 to n do
        if not cx[v] then
          if a[u,v] then
                dfs(v);
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);

    readln(n,m);
    for i:=1 to m do
        begin
            readln(x,y);
            a[x,y]:=true;
            a[y,x]:=true;
        end;

    for i:=1 to n do
        if not cx[i] then
                begin
                    inc(dem);
                    dfs(i);
                end;

    res:=m-n+dem;

    writeln(res);

    close(input);close(output);
end.