[Usaco2008Nov]安慰奶牛cheer

[Usaco2008Nov]安慰奶牛cheer

Time Limit:10000MS Memory Limit:165536K
Total Submit:18 Accepted:15
Case Time Limit:1000MS

Description

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

第j条双向道路连接了牧场S_j和E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j),
而且走完它需要L_j (0 <= L_j <= 1,000)的时间. 没有两个牧场是被一条以上的道路所连接.

奶牛们非常伤心, 因为她们的交通系统被削减了. 你需要到每一个奶牛的住处去安慰她们. 每次
你到达第i个牧场的时候(即使你已经到过), 你必须花去C_i (1 <= C_i <= 1,000)的
时间和奶牛交谈.

你每个晚上都会在同一个牧场(这是供你选择的)过夜, 直到奶牛们都从悲伤中缓过神来. 在早上
起来和晚上回去睡觉的时候, 你都需要和在你睡觉的牧场的奶牛交谈一次. 这样你才能完成你的
交谈任务.

假设Farmer John采纳了你的建议, 请计算出使所有奶牛都被安慰的最少时间.

对于你前10次的提交, 你的程序会在一部分正式的测试数据上运行, 并且返回运行的结果.

程序名: cheer

Input

* 第 1 行: 用空格隔开的两个整数N和P
* 第 2..N+1 行: 第i+1行包含了一个整数: C_i
* 第 N+2..N+P+1 行: 第 N+j+1 行包含用空格隔开的三个整数: S_j, E_j 和 L_j

Output

第 1 行: 一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间).

Sample Input

Sample Output

Source
饿..这道题还是有点意思的…首先要我们求一个生成树..那么尝试着转化成最小生成树问题,对于每条边,如果选的话,则要耗去来回一趟和访问2个端点的时间,重加一下权就可以了,最后选择最小的哪个节点当出发点就行了。..
Code:

#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000;int n,m;struct uf{ int F[maxn]; uf(){rep(i,n)F[i]=i;} int Find(int i) { return i==F[i]?i:(F[i]=Find(F[i])); } bool Find(int i,int j) { i=Find(i);j=Find(j); return F[i]=j,i!=j; }};struct Edge{ int s,t,c; Edge(int _s,int _t,int _c):s(_s),t(_t),c(_c){} bool operator<(const Edge&o)const { return c>o.c; }};priority_queue<Edge> PQ;int C[maxn];int main(){ //freopen("in","r",stdin); cin>>n>>m;int s,t,c,ans=~0U>>1; rep(i,n)scanf("%d",C+i),ans<?=C[i]; rep(i,m)scanf("%d%d%D",&s,&t,&c),–s,–t,PQ.push(Edge(s,t,c*2+C[s]+C[t])); uf U; while(n>1) { Edge e=PQ.top();PQ.pop(); if(U.Find(e.s,e.t)) ans+=e.c,n–; } cout<<ans<<endl;}176输出解释:保持这些路径: 1-(5)-2-(5)-3 5 / (12) /(12) *4——+从牧场4起床, 然后按照 4, 5, 4, 2, 3, 2, 1, 2, 4 的顺序来访问奶牛们, 总共需要176个单位的时间.5 71010206301 2 52 3 52 4 123 4 172 5 153 5 64 5 12输入解释: +-(15)-+ / / 1-(5)-2-(5)-3-(6)–5 /(17) / (12) / /(12) 4——+

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>