1601: [Usaco2008 Oct]灌水
2024-10-11 22:55:23
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不解释
var
i,j,k,l,m,n:longint;
a:array[..,..] of longint;
b:array[..] of longint;
c:array[..,..] of longint;
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end; procedure sort(l,r:longint);
var
i,j,x,y:longint;
begin
i:=l;
j:=r;
x:=c[(i+j) div ,];
repeat
while c[i,]<x do inc(i);
while c[j,]>x do dec(j);
if i<=j then
begin
swap(c[i,],c[j,]);
swap(c[i,],c[j,]);
swap(c[i,],c[j,]);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function getfat(x:longint):longint;
begin
while b[x]<>x do x:=b[x];
exit(x);
end;
procedure merge(x,y:longint);
begin
b[getfat(x)]:=getfat(y);
end;
function tog(x,y:longint):boolean;
begin
exit(getfat(x)=getfat(y));
end; begin
readln(n);
for i:= to n do
begin
readln(a[,i]);
a[i,]:=a[,i];
end;
for i:= to n do
begin
for j:= to n do
read(a[i,j]);
readln;
end;
m:=;
for i:= to n do
b[i]:=i;
for i:= to n do
for j:= to n do
begin
if a[i,j]> then
begin
inc(m);
c[m,]:=i;
c[m,]:=j;
c[m,]:=a[i,j];
end;
end;
sort(,m);
j:=;
l:=;
for i:= to n do
begin
while tog(c[j,],c[j,]) do
inc(j);
merge(c[j,],c[j,]);
l:=l+c[j,];
inc(j); end;
writeln(l);
end.
最新文章
- 修改Windows Server 2008+IIS 7+ASP.NET默认连接限制,支持海量并发连接数
- spring mvc 入门配置
- 使用CSS将图片转换成黑白(灰色、置灰)z转
- 【转】在Eclipse中建立第一个Servlet程序
- Delphi-UpperCase 函数
- Java学习02
- OpenCV局部变形算法探究
- Django(三) ORM操作
- 20165319 Exp6 信息收集与漏洞扫描
- C#-Database-连接
- Understanding Favicon
- oracle中to_timestamp和to_date什么区别
- JQuery Mobile - 固定住页面和页脚
- CRM 各种类型字段的 赋值 取值
- .net 上传文件大小限制
- Java学习笔记整理第一章 java基本数据类型、修饰符、运算符
- vue10行代码实现上拉翻页加载更多数据,纯手写js实现下拉刷新上拉翻页不引用任何第三方插件
- php多进程pcntl学习(一)
- Maven常用指令
- android笔记---百度地图api应用 (一)