算法训练安慰奶牛

时间限制：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的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第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。

普利姆算法用堆优化后跟库鲁斯卡尔的时间复杂度是一样的，都是Elog(V)。但我在网上没有看到用stl的优先队列来写普利姆的代码，借用stl，代码非常简洁,并且时间复杂度也不高。

这个题实际上是个变形的最小生成树的题，他给每个顶点也加上了花费，但本质上不变，实际上只是每一条路的花费改变了，仔细模拟几遍应该能发现利用每一条边和两个端点能找到每一条边的实际花费。因为要回到那个点睡觉，所以出发之后还需要返回，那么每条边是走了两次，然后再加上两个端点，实际花费是 t3*2+c[t1]+c[t2];

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#define max_v 50005
#define max_e 500005
#define INF 0x3f3f3f3f

using namespace std;

struct edge{int to,cost;};
typedef pair<int,int> P;//first集合X到i的最短距离,second点的编号
int ranchNumber,roadNumber;//顶点个数，道路个数
int c[10005];
int mincost[10005];
bool used[10005];
vector<edge> g[100005];

int heapPrime(){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(mincost,mincost+10005,INF);
    fill(used,used+10005,false);
    mincost[0]=0;
    int ans=0;
    que.push(P(mincost[0],0));
    for(int j=0;j<ranchNumber;j++){
        P p=que.top();
        while(used[p.second]==true){
            que.pop();
            p=que.top();
        }
        que.pop();
        used[p.second]=true;
        ans+=p.first;
        int e=p.second;
        for(int i=0;i<g[e].size();i++){
            edge ee=g[e][i];
            if(mincost[ee.to]>ee.cost){
                mincost[ee.to]=ee.cost;
                que.push(P(mincost[ee.to],ee.to));
            }
        }
    }
    return ans;
}

int main()
{
    int minn=INF;
    scanf("%d %d",&ranchNumber,&roadNumber);
    for(int i=0;i<ranchNumber;i++){
        scanf("%d",&c[i]);
        minn=min(minn,c[i]);
    }
    int t1,t2,t3;
    for(int i=0;i<roadNumber;i++){
        scanf("%d %d %d",&t1,&t2,&t3);
        t1-=1;
        t2-=1;
        t3=t3*2+c[t1]+c[t2];
        edge tem;
        tem.to=t2;
        tem.cost=t3;
        g[t1].push_back(tem);
        tem.to=t1;
        g[t2].push_back(tem);
    }
    int ans=heapPrime();
    printf("%d",ans+minn);
    return 0;
}
/*
10 25
22
4
96
26
33
79
2
2
80
43
2 6 39
1 8 62
1 7 1
2 3 46
1 4 6
3 6 14
9 8 90
6 1 88
7 2 19
2 5 29
4 7 99
4 3 48
5 9 74
3 7 98
4 6 88
1 5 29
10 9 12
2 1 83
8 10 8
7 5 85
8 5 50
6 9 44
8 3 64
6 8 86
5 6 2
*/