专栏首页HansBug's Lab1601: [Usaco2008 Oct]灌水

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 条评论
登录 后参与评论

相关文章

  • 算法模板——计算几何2(二维凸包——Andrew算法)

    实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反...

    HansBug
  • 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

    1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 Time Limit: 10 Sec  Memory Limit: 64 M...

    HansBug
  • 2818: Gcd

    2818: Gcd Time Limit: 10 Sec  Memory Limit: 256 MB Submit: 2170  Solved: 979 [Su...

    HansBug
  • 算法模板——计算几何2(二维凸包——Andrew算法)

    实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反...

    HansBug
  • 1131: [POI2008]Sta

    1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

    HansBug
  • 算法-买卖股票的最佳时机 II

    版权声明: ...

    Fisherman渔夫
  • 3522: [Poi2014]Hotel

    3522: [Poi2014]Hotel Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 253  Solve...

    HansBug
  • 2292: 【POJ Challenge 】永远挑战

    2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

    HansBug
  • matlab绘图(一)

    matlab除了强大计算功能之外,其绘图功能也是不容小觑的。平时大家计算的结果常常需要以图形的方式给他人展示,今天就给大家介绍几个matlab最基本的二维绘图命...

    艾木樨
  • Spring源码-父子容器

    秋日芒草

扫码关注云+社区

领取腾讯云代金券