1601: [Usaco2008 Oct]灌水

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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1692: [Usaco2007 Dec]队列变换(BZOJ1640强化版)

1692: [Usaco2007 Dec]队列变换 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 682  So...

2915
来自专栏小樱的经验随笔

BZOJ 1597: [Usaco2008 Mar]土地购买【斜率优化+凸包维护】

1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 4989 ...

2936
来自专栏HansBug's Lab

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛 Time Limit: 5 Sec  Memory Limit: 64 MB...

2887
来自专栏HansBug's Lab

2015: [Usaco2010 Feb]Chocolate Giving

2015: [Usaco2010 Feb]Chocolate Giving Time Limit: 10 Sec  Memory Limit: 162 MB S...

3136
来自专栏HansBug's Lab

3301: [USACO2011 Feb] Cow Line

3301: [USACO2011 Feb] Cow Line Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

32010
来自专栏HansBug's Lab

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 Time Limit: 5 Sec  Memory Limit: 64 M...

2886
来自专栏HansBug's Lab

1664: [Usaco2006 Open]County Fair Events 参加节日庆祝

1664: [Usaco2006 Open]County Fair Events 参加节日庆祝 Time Limit: 5 Sec  Memory Limit:...

2695
来自专栏HansBug's Lab

1682: [Usaco2005 Mar]Out of Hay 干草危机

1682: [Usaco2005 Mar]Out of Hay 干草危机 Time Limit: 5 Sec  Memory Limit: 64 MB Subm...

3454
来自专栏HansBug's Lab

1620: [Usaco2008 Nov]Time Management 时间管理

1620: [Usaco2008 Nov]Time Management 时间管理 Time Limit: 5 Sec  Memory Limit: 64 MB...

3088
来自专栏HansBug's Lab

1634: [Usaco2007 Jan]Protecting the Flowers 护花

1634: [Usaco2007 Jan]Protecting the Flowers 护花 Time Limit: 5 Sec  Memory Limit:...

3268

扫码关注云+社区

领取腾讯云代金券