算法训练 安慰奶牛

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

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

接下来N行，每行包含一个整数C_i。

接下来P行，每行包含三个整数S_j, E_j和L_j。

5 <= N <= 10000，N-1 <= P <= 100000，0 <= L_j <= 1000，1 <= C_i <= 1,000。

思路：

这道题着实把我恶心到了，题目题意表述不清，测试样例错误。

先把正确的输入样例给出来：

5 71010206301 2 52 3 52 4 123 4 172 5 153 5 64 5 12

输出还是 176

题目题意表述不清，刚开始以为是每天只去拜访一家农场，只安慰一头奶牛。然后忽略了一局关键的话：你每个晚上都会在同一个牧场(这是供你选择的)过夜

刚开始的思路是这样的，先按照边权求出一颗最小生成树，然后访问的时候在考虑每个农场安慰的时间

如上图，假设按照边权获得了一颗最小生成树，然后从顶点1出发，按照1~10的顺序去访问，那么每个顶点的访问此书就是自身度数的2倍，遍历一次生成树。但是顶点1要少多1次

早上从1出发，到2，然后在2这里过夜，第二天再从2出发到3...

然后事实成功证明这是错的+_+

关键的话：你每个晚上都会在同一个牧场(这是供你选择的)过夜

按照上图的话，我每晚可能会在不同的农场过夜，如果要在同一个农场过夜，说明每天只能走一个分支然后回来

如上图，1->2->3->2->1在1这里过夜  1->4->1 在1这里过夜  1->5->6->5->1最后回到1

这样的话就能保证每晚在一个农场过夜

但是这样算出来的结果还是错误的，因为边权的数值改变了。如果单纯的之按照输出进来的数值作为边权，的确是一个最小生成树，但是总时间里面还会受到点权的影响，这样得出来的时间并不能够保证是最小值。

所以，边权的数值需要变动。和上面的规律一样，每个点的访问次数是自身点度数的2倍，始点多一次。所以我们可以把点权加入到边权中。一条边的边权等于边权+两端顶点的点权。正好遍历一次每条访问两次。再加上刚开始始点多出来的一次就可以了。

另外，在吐槽一下，为什么我用不压缩路径的并查集得出来的结果差那么多，貌似以前也遇到过这种问题，老老实实用带路径压缩的吧。

AC代码：

#include<iostream>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>using namespace std;const int MAXN=100005;struct node{    int s;//始点    int e;//终点    int comfort_time;//边权}edge[MAXN];//定义边集数组int v[MAXN];//点权int father[MAXN];bool cmp1(node a, node b)//顶点权重比较函数{    return a.comfort_time<b.comfort_time;}int Find(int x){    if(father[x]!=x)    {        int temp=Find(father[x]);        father[x]=temp;        return temp;    }    return x;}int krusal(int N, int P){    sort(edge+1,edge+P+1,cmp1);    int cost=0;    for(int i=0;i<=N;i++)    {        father[i]=i;    }    int cnt=0;    for(int i=1;i<=P;i++)    {        int fe=Find(edge[i].e);        int fs=Find(edge[i].s);        if(fs!=fe)        {            father[fs]=fe;            cost+=edge[i].comfort_time;            cnt++;        }        if(cnt==N-1)            break;    }    return cost;}int main(){    int N,P;    int cnt_time=0;    scanf("%d %d",&N,&P);    for(int i=1;i<=N;i++)        scanf("%d",&v[i]);    for(int i=1;i<=P;i++)    {        scanf("%d %d %d",&edge[i].e,&edge[i].s,&edge[i].comfort_time);        edge[i].comfort_time=2*edge[i].comfort_time+v[edge[i].e]+v[edge[i].s];    }    cnt_time+=krusal(N,P);    sort(v+1,v+N+1);    cnt_time+=v[1];    PRintf("%d/n",cnt_time);    return 0;}第一种想法的代码（警戒自己）：
#include<iostream>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>using namespace std;const int MAXN=100005;struct node{    int s;//始点    int e;//终点    int comfort_time;//边权}edge[MAXN];//定义边集数组struct vertex{    int weight;//点权    int postion;//输入进来时候的位置}v[MAXN];//定义每个点自身花费的时间int father[MAXN];int flag[MAXN];//标记数组int du[MAXN];//顶点的度数bool cmp1(node a, node b)//顶点权重比较函数{    return a.comfort_time<b.comfort_time;}bool cmp2(vertex a, vertex b)//边权比较函数{    return a.weight<b.weight;}bool check(int N)//检查是否所有的点都已经遍历完成{    for(int i=1;i<=N;i++)        if(!flag[i])            return false;    return true;}int Find(int x){    if(father[x]!=x)        father[x]=Find(father[x]);    return father[x];}void unionn(int x, int y){    int fa=Find(x);    int fb=Find(y);    if(fa!=fb)        father[x]=y;}int krusal(int N, int P){    sort(edge+1,edge+P+1,cmp1);    int cost=0;    memset(flag,false,sizeof(flag));    memset(du,0,sizeof(du));    for(int i=0;i<=N;i++)    {        father[i]=i;    }    int index=1;//选择边的下标    while(!check(N))    {        if(Find(edge[index].e)!=Find(edge[index].s))        {            unionn(edge[index].e,edge[index].s);            cost+=edge[index].comfort_time;            flag[edge[index].e]=true;            flag[edge[index].s]=true;            du[edge[index].e]++;            du[edge[index].s]++;        }        index++;    }    return cost;}int main(){    int N,P;    int cnt_time=0;    scanf("%d %d",&N,&P);    for(int i=1;i<=N;i++)    {        scanf("%d",&v[i].weight);        v[i].postion=i;    }    for(int i=1;i<=P;i++)    {        scanf("%d %d %d",&edge[i].e,&edge[i].s,&edge[i].comfort_time);    }    cnt_time+=2*krusal(N,P);    sort(v+1,v+N+1,cmp2);    cnt_time+=(du[v[1].postion]+1)*v[1].weight;    for(int i=2;i<=N;i++)    {        cnt_time+=du[v[i].postion]*v[i].weight;    }    printf("%d/n",cnt_time);    return 0;}