1601: [Usaco2008 Oct]灌水
1601: [Usaco2008 Oct]灌水
HansBug
发布于 2018-04-10 14:29:49
发布于 2018-04-10 14:29:49
1601: [Usaco2008 Oct]灌水
Time Limit: 5 Sec Memory Limit: 162 MB Submit: 1342 Solved: 881 [Submit][Status]
Description
Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。
Input
*第一行：一个数n
*第二行到第n+1行：第i+1行含有一个数wi
*第n+2行到第2n+1行：第n+1+i行有n个被空格分开的数，第j个数代表pij。
Output
*第一行：一个单独的数代表最小代价.
Sample Input
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
Sample Output
9
输出详解：
Farmer John在第四块土地上建立水库，然后把其他的都连向那一个，这样就要花费3+2+2+2=9
HINT
Source
题解：一个萌萌的最小生成树——唯一的关键就是应该再额外建立一个节点，然后连接各个可以建水库的点，然后别的点该怎么连怎么连，然后直接上MST，Accept不解释
1 var
2 i,j,k,l,m,n:longint;
3 a:array[0..1000,0..1000] of longint;
4 b:array[0..1000] of longint;
5 c:array[0..100000,1..3] of longint;
6 procedure swap(var x,y:longint);
7 var z:longint;
8 begin
9 z:=x;x:=y;y:=z;
10 end;
11
12 procedure sort(l,r:longint);
13 var
14 i,j,x,y:longint;
15 begin
16 i:=l;
17 j:=r;
18 x:=c[(i+j) div 2,3];
19 repeat
20 while c[i,3]<x do inc(i);
21 while c[j,3]>x do dec(j);
22 if i<=j then
23 begin
24 swap(c[i,1],c[j,1]);
25 swap(c[i,2],c[j,2]);
26 swap(c[i,3],c[j,3]);
27 inc(i);dec(j);
28 end;
29 until i>j;
30 if i<r then sort(i,r);
31 if l<j then sort(l,j);
32 end;
33 function getfat(x:longint):longint;
34 begin
35 while b[x]<>x do x:=b[x];
36 exit(x);
37 end;
38 procedure merge(x,y:longint);
39 begin
40 b[getfat(x)]:=getfat(y);
41 end;
42 function tog(x,y:longint):boolean;
43 begin
44 exit(getfat(x)=getfat(y));
45 end;
46
47
48
49 begin
50 readln(n);
51 for i:=1 to n do
52 begin
53 readln(a[0,i]);
54 a[i,0]:=a[0,i];
55 end;
56 for i:=1 to n do
57 begin
58 for j:=1 to n do
59 read(a[i,j]);
60 readln;
61 end;
62 m:=0;
63 for i:=0 to n do
64 b[i]:=i;
65 for i:=0 to n do
66 for j:=0 to n do
67 begin
68 if a[i,j]>0 then
69 begin
70 inc(m);
71 c[m,1]:=i;
72 c[m,2]:=j;
73 c[m,3]:=a[i,j];
74 end;
75 end;
76 sort(1,m);
77 j:=1;
78 l:=0;
79 for i:=1 to n do
80 begin
81 while tog(c[j,1],c[j,2]) do
82 inc(j);
83 merge(c[j,1],c[j,2]);
84 l:=l+c[j,3];
85 inc(j);
86
87 end;
88 writeln(l);
89 end.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-12-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读