bzoj1601【Usaco2008 Oct】灌水

1601: [Usaco2008 Oct]灌水

Time Limit: 5 Sec  Memory Limit: 162 MB

Submit: 1589  Solved: 1035

[Submit][Status][Discuss]

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

资格赛

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 305
#define inf 1000000000
using namespace std;
int n,tmp,ans,d[maxn],g[maxn][maxn];
bool vst[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();
	memset(vst,false,sizeof(vst));
	F(i,1,n) d[i]=read();
	d[0]=inf;
	F(i,1,n) F(j,1,n) g[i][j]=read();
	F(i,1,n)
	{
		tmp=0;
		F(j,1,n) if (!vst[j]&&d[j]<d[tmp]) tmp=j;
		ans+=d[tmp];
		vst[tmp]=true;
		F(j,1,n) if (!vst[j]) d[j]=min(d[j],g[tmp][j]);
	}
	printf("%d\n",ans);
}
时间: 02-05

bzoj1601【Usaco2008 Oct】灌水的相关文章

BZOJ1601: [Usaco2008 Oct]灌水

1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MBSubmit: 1280  Solved: 839[Submit][Status] Description Farmer John已经决定把水灌到他的n(1<=n<=300)块农田,农田被数字1到n标记.把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库. 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1

[BZOJ1601] [Usaco2008 Oct] 灌水 (kruskal)

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行到

【最小生成树】Bzoj1601[Usaco2008 Oct]灌水

Description Farmer John已经决定把水灌到他的n(1<=n<=300)块农田,农田被数字1到n标记.把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库. 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价. Sulotion 直接搞好像不太好做?于是新设一个点,作为总水源,和i点边权为wi,然后直接求

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

BZOJ——1601: [Usaco2008 Oct]灌水

http://www.lydsy.com/JudgeOnline/problem.php?id=1601 Time Limit: 5 Sec  Memory Limit: 162 MBSubmit: 2156  Solved: 1416[Submit][Status][Discuss] Description Farmer John已经决定把水灌到他的n(1<=n<=300)块农田,农田被数字1到n标记.把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库. 建造一个水库需要花费

[Usaco2008 Oct]灌水

题目描述 Farmer John已经决定把水灌到他的n(1<=n<=300)块农田,农田被数字1到n标记.把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库. 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价. 输入格式 *第一行:一个数n *第二行到第n+1行:第i+1行含有一个数wi *第n+2行到第2n+1行:第

【题解】[Usaco2008 Oct]灌水

题啥意思我也不说了,是个人应该都看得懂 我的做法是这个样子的: 设第i个为了灌到水的代价为cost[i] 每次在i块农田里选第k块还未确定的.花费最少的农田的代价把它设为确定的 再以这块农田向周围的农田引水 重复以上三个步骤即可,代码如下: #include<iostream> using namespace std; int n,w[301],cost[301],book[301]; int p[301][301],k,ans; int main() { cin>>n; for(

【BZOJ】1601: [Usaco2008 Oct]灌水

[算法]最小生成树 [题解] 想到网络流,但是好像不能处理流量和费用的关系. 想到最短路,但好像不能处理重复选边的问题. 每条边只需要选一次,每个点就要遍历到,可以想到最小生成树. 建超级源向每个点连边,点与点连边,对n+1个点求最小生成树(MST)即可. #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=310; int n,first[

BZOJ 1601: [Usaco2008 Oct]灌水( MST )

MST , kruskal 直接跑 ---------------------------------------------------------------------- #include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<iostream> #define rep( i , n ) for( int i = 0 ; i <

BZOJ 1601 Usaco2008 Oct 灌水 Prim

题目大意:给定n个点,每个点可以花w[i]的代价建水井,或者花p[i][j]的代价连接到一个已经供水的点,求最小花销 将每个点向超级源连一条边,边权为w[i] 求最小生成树即可 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 310 using namespace std; int n,map[M][M]; int Prim(int