FWATER spoj - Tưới nước đồng cỏ

Nguồn đề bài: http://vn.spoj.com/problems/FWATER/

1. Đề bài FWATER spoj

Nông dân John quyết định mang nước tới cho N (1 <= N <= 300) đồng cỏ của mình, để thuận tiện ta đánh số các đồng cỏ từ 1 đến N. Để tưới nước cho 1 đồng cỏ John có thể chọn 2 cách, 1 là đào ở đồng cỏ đó 1 cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ trước đó đã có nước tới.

Để đào một cái giếng ở đồng cỏ i cần 1 số tiền là W_i (1 <= W_i <= 100,000). Lắp ống dẫn nước nối 2 đồng cỏ i và j cần 1 số tiền là P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Tính xem nông dân John phải chi ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.

DỮ LIỆU

Dòng 1: Một số nguyên duy nhất: N
Các dòng 2..N + 1: Dòng i+1 chứa 1 số nguyên duy nhất: W_i
Các dòng N+2..2N+1: Dòng N+1+i chứa N số nguyên cách nhau bởi dấu cách; số thứ j là P_ij

KẾT QUẢ

Dòng 1: Một số nguyên duy nhất là chi phí tối thiểu để cung cấp nước cho tất cả các đồng cỏ.

VÍ DỤ

Dữ liệu
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Kết quả
9

2. Giải thích FWATER spoj

Có 4 đồng cỏ. Mất 5 tiền để đào 1 cái giếng ở đồng cỏ 1, 4 tiền để đào ở đồng cỏ 2, 3 và 3 tiền để đào ở đồng cỏ 4. Các ống dẫn nước tốn 2, 3, và 4 tiền tùy thuộc vào nó nối đồng cỏ nào với nhau.

Nông dân John có thể đào 1 cái giếng ở đồng cỏ thứ 4 và lắp ống dẫn nối đồng cỏ 1 với tất cả 3 đồng cỏ còn lại, chi phí tổng cộng là 3 + 2 + 2 + 2 = 9.

3. Hướng dẫn FWATER spoj

– Xây dựng thêm 1 đỉnh N+1 có cạnh nối với i (i=1..n) chính là chi phí của giếng nước thứ i.

– Sau đó tìm cây khung có trọng số nhỏ nhất. ở đây có thể dùng Prim hoặc Kruskal đều được.

4. Code tham khảo FWATER spoj

const   fi='FWATER.inp';
        nmax=301;
type    data=longint;
        dulieu=record
                u,v,c:data;
        end;

var
        f:text;
        B:array[1..300*300] of dulieu;
        A:array[0..nmax+1,0..nmax+1] of data;
        n,m:data;
        root:array[0..nmax+1] of data;

procedure docfile;
var     i,j,u,v,c:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        fillchar(a,sizeof(a),0);
        for i:=1 to n do
                begin
                        readln(f,c);
                        a[n+1,i]:=c;
                        a[i,n+1]:=c;
                end;
        for i:=1 to n do
                for j:=1 to n do
                        read(f,a[i,j]);
        n:=n+1;
        m:=0;
        for i:=1 to n-1 do
                for j:=i+1 to n do
                        begin
                                inc(m);
                                with b[m] do
                                        begin
                                                u:=i;
                                                v:=j;
                                                c:=a[i,j];
                                        end;
                        end;
        close(f);
end;

procedure sort(l,r: longint);
      var
         x,i,j: longint;
         y:dulieu;
      begin
         i:=l;
         j:=r;
         x:=b[(l+r) div 2].c;
         repeat
           while b[i].c<x do inc(i);
           while x<b[j].c do dec(j);
           if not(i>j) then
             begin
                y:=b[i];
                b[i]:=b[j];
                b[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure union(a,b:data);
begin
        root[a]:=b;
end;

function findroot(x:data):data;
begin
        if root[x]<>x then
                root[x]:=findroot(root[x]);
        exit(root[x]);
end;

procedure kruskal;
var     i,j,u,v,res:data;
begin
        for i:=1 to n do
                root[i]:=i;
        res:=0;
        for i:=1 to m do
                begin
                        u:=findroot(b[i].u);
                        v:=findroot(b[i].v);
                        if u<>v then
                                begin
                                        union(u,v);
                                        res:=res+b[i].c;
                                end;
                end;
        writeln(res);
end;

begin
        docfile;
        sort(1,m);
        kruskal;
        readln;
end.

FWATER spoj – Tưới nước đồng cỏ