289
藍橋杯 算法訓練 安慰奶牛
算法訓練 安慰奶牛
時間限製：1.0s 內存限製：256.0M
問題描述
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 6
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
樣例輸出
178
數據規模與約定
5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。
思路：奶牛的牧場之間是一棵樹，會發現，對於每條邊，我們花費的時間是二倍的邊權值加上兩
個端點的權值。將每條邊(a, b)的權值Lj改變為2Lj+Ca+Cb，然後使用最小生成樹來計算。
至於選擇過夜的地方，根據題意，最後要多花費一個點權。找最小的即可
注意：藍橋杯給的測試數據是錯誤的，正確的請看上麵的測試數據！！
AC代碼：#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
int a,b;
int len;
}per[100010];
int cmp(node x,node y)
{
if(x.len!=y.len) return x.len<y.len;
}
int Time[10010];
int main()
{
int i,j,n,m,flag[10010],sum,num;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%d",&Time[i]);
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&per[i].a,&per[i].b,&per[i].len);
per[i].len=Time[per[i].a-1]+Time[per[i].b-1]+per[i].len*2;
}
sort(per,per+m,cmp);
for(i=1;i<=n;i++) flag[i]=1;
flag[per[0].a]=0;
sum=0;
for(i=0;i<m;i++)
{
num=flag[per[i].a]+flag[per[i].b];
if(num==1)
{
sum+=per[i].len;
flag[per[i].a]=flag[per[i].b]=0;
i=0;
}
}
sort(Time,Time+n);
printf("%d\n",sum+Time[0]);
return 0;
}
最後更新：2017-04-03 12:55:04