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

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

Nội dung bài viết

1. Đề bài FWATER spoj
2. Giải thích FWATER spoj
3. Hướng dẫn FWATER spoj
4. Code tham khảo FWATER spoj

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.

100

101

102

103

104

105

106

107

108

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;

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;

writeln(res);

end;

begin

docfile;

sort(1,m);

kruskal;

readln;

end.

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

1. Đề bài FWATER spoj

DỮ LIỆU

KẾT QUẢ

VÍ DỤ

2. Giải thích FWATER spoj

3. Hướng dẫn FWATER spoj

4. Code tham khảo FWATER spoj

Bài viết liên quan

Trả lời Hủy