安慰奶牛

问题描述

Farmer John变得非常懒,他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场,牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路,但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej),而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心,因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过),你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜,直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候,你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议,请计算出使所有奶牛都被安慰的最少时间。

输入格式

第1行包含两个整数N和P。

接下来N行,每行包含一个整数Ci。

接下来P行,每行包含三个整数Sj, Ej和Lj。

输出格式

输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。

样例输入

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6

样例输出

176

数据规模与约定

5 <= N <= 10000,N-1 <= P <= 100000,0 <= Lj <= 1000,1 <= Ci <= 1,000。

这个就是那个生成树的题目。我就是用的 刚才那篇文章的方法求解的生成树。无奈,非常悲剧的是我用邻接表存储无向图远远的超出了内存限制。因此只能做出前三个题目。。。

因为我的数组开的很小,题目要求10000,我只开了100.

这个题目理解起来还挺奇怪的什么睡觉不睡觉的,反正我是没有看懂。不过这题也说明了一个点权可以转化为边权来计算。首先他说要去掉一些没有必要的路,这样的话很自然的就想到了最小生成树啦。然后我就学习了用邻接表存无向图的最小生成树方法。还有题目中说安慰牛要花费时间,走路上要花费时间,所以选择一条道路花费的时间是一条路的时间的两倍再加上两个点的时间。然后要在起点睡一觉,所以起点的牛要多安慰一遍,为了使结果最小,就选安慰时间最少的点作为起点。然后就有了下面的代码。

 1 #include<iostream>
 2 using namespace std;
 3 const int in = 1000;
 4 int main()
 5 {
 6     int N,P;
 7     int c[101];
 8     int l[101][101] = {0};
 9     cin >>N>>P;
10     int i;
11     for(i = 0;i < N;i++)
12     {
13         cin >> c[i];
14     }
15     int j,k;
16     for(k = 0;k < P;k++)
17     {
18         int c;
19         cin >>i>>j;
20         cin>>c;
21         l[i - 1][j - 1] = l[j - 1][i - 1] = c;
22     }
23     int map[101][101];
24     for(i = 0;i < N;i++)
25     {
26         for(j = 0;j < N;j++)
27         {
28             if(l[i][j] == 0)map[i][j] = in;
29             else map[i][j] = 2*l[i][j]+c[i]+c[j];
30         }
31     }
32     int cost[101];
33     int point[101];
34     bool visit[101];
35     for(i = 0;i < N;i++)
36     {
37         cost[i] = map[0][i];
38         point[i] = 0;
39         visit[i] = false;
40     }
41     visit[0] = true;
42     for(k = 1;k<N;k++)
43     {
44         int min = in;
45         j = 0;
46         for(i = 0;i < N;i++)
47         {
48             if(!visit[i] && min > cost[i]){min = cost[i];j = i;}
49         }
50         visit[j] = true;
51         for(i = 0;i < N;i++)
52         {
53             if(!visit[i] && cost[i] > map[j][i]){cost[i] = map[j][i];point[i] = j;}
54         }
55     }
56     int min = c[0];
57     for(i = 0;i < N;i++)
58     {
59         if(min > c[i])min = c[i];
60     }
61     int sum = 0;
62     for(i = 1;i < N;i++)
63     {
64         sum += map[i][point[i]];
65     }
66     cout<<sum+min<<endl;
67     return 0;
68 }

这样显然是不行的,因为二阶矩阵实在是太大了。所以就用链表存储该图。但是用链表存储的最小生成树算法我并不会写。先粘一个通过的代码。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN=10000+10;
 6 const int MAXM=100000+10;
 7 const int INF=100000;
 8 int cost[MAXN],fa[MAXN];
 9 int find(int cur)
10 {
11   return cur==fa[cur]? cur:fa[cur]=find(fa[cur]);
12 }
13 struct edge
14 {
15   int from,to,val;
16   bool operator <(const edge& x)const{
17     return val<x.val;
18   }
19 }e[MAXM];
20
21 int main()
22 {
23   int mini=INF,index;
24   int n,p;
25   scanf("%d%d",&n,&p);
26   for(int i=1;i<=n;i++)
27   {
28     scanf("%d",&cost[i]);
29     mini=min(cost[i],mini);
30     fa[i]=i;
31   }
32   for(int i=0;i<p;i++)
33   {
34     scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);
35     e[i].val=(e[i].val<<1)+cost[ e[i].from ] + cost [ e[i].to ];
36   }
37   sort(e,e+p);
38   int ans=0;
39   for(int i=0;i<p;i++)
40   {
41     int x=e[i].from,y=e[i].to;
42     int root_x=find(x),root_y=find(y);
43     if(root_x==root_y)   continue;
44     fa[root_x]=root_y;
45     ans+=e[i].val;
46   }
47   printf("%d\n",ans+mini);
48   return 0;
49 }

等我再研究一下用链表的怎么写。

时间: 05-24

安慰奶牛的相关文章

蓝桥杯 安慰奶牛

算法训练 安慰奶牛 时间限制:1.0s   内存限制:256.0MB 锦囊1 使用最小生成树算法. 锦囊2 将每条边(a, b)的权值Lj改变为2Lj+Ca+Cb,然后使用最小生成树来计算. 问题描述 Farmer John变得非常懒,他不想再继续维护供奶牛之间供通行的道路.道路被用来连接N个牧场,牧场被连续地编号为1到N.每一个牧场都是一个奶牛的家.FJ计划除去P条道路中尽可能多的道路,但是还要保持牧场之间 的连通性.你首先要决定那些道路是需要保留的N-1条道路.第j条双向道路连接了牧场Sj和

蓝桥杯训练 安慰奶牛 (Kruskal MST)

算法训练 安慰奶牛 时间限制:1.0s   内存限制:256.0MB 问题描述 Farmer John变得非常懒,他不想再继续维护供奶牛之间供通行的道路.道路被用来连接N个牧场,牧场被连续地编号为1到N.每一个牧场都是一个奶牛的家.FJ计划除去P条道路中尽可能多的道路,但是还要保持牧场之间 的连通性.你首先要决定那些道路是需要保留的N-1条道路.第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej),而且走完它需要Lj的时间.

蓝桥杯试题 算法训练 安慰奶牛

算法训练 安慰奶牛 时间限制:1.0s   内存限制:256.0MB 问题描述 Farmer John变得非常懒,他不想再继续维护供奶牛之间供通行的道路.道路被用来连接N个牧场,牧场被连续地编号为1到N.每一个牧场都是一个奶牛的家.FJ计划除去P条道路中尽可能多的道路,但是还要保持牧场之间 的连通性.你首先要决定那些道路是需要保留的N-1条道路.第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej),而且走完它需要Lj的时间.

bzoj1232[Usaco2008Nov]安慰奶牛cheer*

bzoj1232[Usaco2008Nov]安慰奶牛cheer 题意: 给出n个节点的带权图,第i个节点ci.现在你要在这个图中选出一棵树和一个起点,然后你要从起点出发到达所有的节点(不能跳点)再回到起点,经过边的时间为边权,每经过一个点就要花等同于点权的时间(即使这个点已经过).问如何使时间最短.n≤10000. 题解: 每条边的边权为这条边原来的边权加两个端点的点权(因为每个点都要经过两次),然后做最小生成树. 代码: 1 #include <cstdio> 2 #include <

算法训练 安慰奶牛

[原][Usaco Nov08 Gold] 安慰奶牛 2014-5-26阅读159 评论0 Description Farmer John变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接N (5 <= N <= 10,000)个牧场, 牧场被连续地编号为1..N. 每一个牧场都是一个奶牛的家. FJ计划除去P(N-1 <= P <= 100,000)条道路中尽可能多的道路, 但是还要保持牧场之间的连通性. 你首先要决定那些道路是需要保留的N-1条道路. 第j条

1232: [Usaco2008Nov]安慰奶牛cheer

1232: [Usaco2008Nov]安慰奶牛cheer Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 612  Solved: 431[Submit][Status] Description Farmer John变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接N (5 <= N <= 10,000)个牧场, 牧场被连续地编号为1..N. 每一个牧场都是一个奶牛的家. FJ计划除去P(N-1 <= P <=

蓝桥杯 - 安慰奶牛 (最小生成树)

题目传送:蓝桥杯 - 安慰奶牛 思路:先算好边的权值,为本来的边的权值的两倍加上两个点的权值,再进行kruskal,因为边数较大,不宜采用prim AC代码: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define LL long long #define INF 0x7fffffff const in

33-算法训练 安慰奶牛 - 对象数组排序,对象链表转数组

算法训练 安慰奶牛 时间限制:1.0s   内存限制:256.0MB 问题描述 Farmer John变得非常懒,他不想再继续维护供奶牛之间供通行的道路.道路被用来连接N个牧场,牧场被连续地编号为1到N.每一个牧场都是一个奶牛的家.FJ计划除去P条道路中尽可能多的道路,但是还要保持牧场之间 的连通性.你首先要决定那些道路是需要保留的N-1条道路.第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej),而且走完它需要Lj的时间.

[USACO08NOV]安慰奶牛Cheering up the Cow

这个题一看就是最小生成树,但是这题关键是确定边权. 首先为了安慰奶牛,一定要遍历每个奶牛并且回到起点,所以每条边会被经过两次,而为了通过这条边必须和两端点奶牛谈话,因此要再加上两端点的c值.综上(i,j)边权为l(i,j)  * 2 + c_i + c_j. #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define N 10010 #define M 1000

算法训练 安慰奶牛 &#160; 最小生成树

问题描述 Farmer John变得非常懒,他不想再继续维护供奶牛之间供通行的道路.道路被用来连接N个牧场,牧场被连续地编号为1到N.每一个牧场都是一个奶牛的家.FJ计划除去P条道路中尽可能多的道路,但是还要保持牧场之间 的连通性.你首先要决定那些道路是需要保留的N-1条道路.第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej),而且走完它需要Lj的时间.没有两个牧场是被一条以上的道路所连接.奶牛们非常伤心,因为她们的交通系