洛谷P1550 [USACO08OCT]打井Watering Hole
P1550 [USACO08OCT]打井Watering Hole
题目背景
John的农场缺水了!!!
题目描述
Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.
Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).
Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).
Determine the minimum amount Farmer John will have to pay to water all of his pastures.
POINTS: 400
农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若
干井,并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。
请求出农民John 需要为连通整个牧场的每一块田地所需要的钱数。
输入输出格式
输入格式:
第1 行为一个整数n。
第2 到n+1 行每行一个整数,从上到下分别为W_1 到W_n。
第n+2 到2n+1 行为一个矩阵,表示需要的经费(P_ij)。
输出格式:
只有一行,为一个整数,表示所需要的钱数。
输入输出样例
说明
John等着用水,你只有1s时间!!!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 310
using namespace std;
int n,fa[maxn],num;
struct node{
int from,to,v;
bool operator < (const node &a)const{
return v<a.v;
}
}e[maxn*maxn];
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
int main(){
scanf("%d",&n);
int x;
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=n;i++){
scanf("%d",&x);
e[++num].from=;e[num].to=i;e[num].v=x;
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&x);
if(i>j)e[++num].from=i,e[num].to=j,e[num].v=x;
}
}
sort(e+,e+num+);
int ans=;
for(int i=;i<=num;i++){
int f1=find(e[i].from),f2=find(e[i].to);
if(f1!=f2){
ans+=e[i].v;
fa[f1]=f2;
}
}
printf("%d",ans);
return ;
}
最新文章
- JS验证码
- Asp.Net MVC及Web API框架配置会碰到的几个问题及解决方案
- linux网站服务Apache+php+mysql的安装
- 阿里云 OSS+CDN
- ASP.NET MVC 微信公共平台开发之 微信接入
- java获取泛型的真实类型
- HDU 3791
- docker一些命令
- 大型网站的架构设计问题&mdash;-大型高并发高负载网站的系
- 案例:计算1!+2!+3!+......+n!
- HDU 1796 Howmany integers can you find (容斥原理)
- @Html.ValidationSummary()的使用
- 如何写对kubernetes的模板文件
- python六十五课——单元测试(一)
- 织梦移动版页面点击下一篇获取不到id
- dll反编译工具总结
- BZOJ4990 [Usaco2017 Feb]Why Did the Cow Cross the Road II 动态规划 树状数组
- lnmp重置密码
- typeScript入门基础 (1)
- 浅谈System.gc()