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ỏ đó ...
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
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 | 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. |
