博客

问题描述

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

4 5 12

样例输出

176

数据规模与约定

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

首先这个题是最小生成树问题，但是没有现成的生成树，所以我们就先构造一个。对于每条边，如果选的话，则要耗去来回一趟和访问2个端点所用的的时间总合，所以将图中各个边的权值改为边本来的权值的两倍加上访问两端点的值，这样一棵树就构造好。至于住在哪间房里面，选择Ci最小的那一间就可以了。

接下来就是运用最小生成树的算法，在我用kruscal算法的过程中，也发现了我以前写这个算法的一个错误，虽然花了我很多时间去找这个错误。。。但是以后肯定是不会再错了，总之这道题还是很有收获的。

#include <stdio.h>
#include <stdlib.h>

struct node 
{
	int x, y;
	int w;
};
node s[100010];
int l, sum;
int f[10010];
int talk[10010];

void init()
{
	int i;
	for(i = 0; i < 10010; i++)
		f[i] = i;
}

int cmp(const void *a, const void *b)
{
	return (((node *)a)->w - ((node *)b)->w);
}

void kruscal(int n)
{
	int q;
	qsort(s, l, sizeof(s[0]), cmp);
	int num = 1, i, j;
	int k = 0;
	while(num < n)
	{
		if(f[s[k].x] != f[s[k].y])
		{
			num++;
			sum += s[k].w;
			//printf("%d - %d = %d, sum = %d\n", s[k].x, s[k].y, s[k].w, sum);
			q = f[s[k].y];
			for(j = 1; j <= n; j++)
			{
				if(f[j] == q)//之前这里写的是if(f[j] == f[s[k].y]),结果都是WA
					f[j] = f[s[k].x];
			}
		}
		k++;
	}
	
}

int main (void)
{
	int n, p, i;
	while(scanf("%d %d", &n, &p) != EOF)
	{
		init();
		l = 0;
		sum = 0;
		int min = 9999;
		for(i = 1; i <= n; i++)
		{
			scanf("%d", &talk[i]);
			if(min > talk[i])
				min = talk[i];
		}
		int temp;
		for(i = 0; i < p; i++)
		{
			scanf("%d %d %d", &s[l].x, &s[l].y, &temp);
			s[l].w = talk[s[l].x] + talk[s[l].y] + 2 * temp;
			l++;
		}
		/*
		for(i = 0; i < l; i++)
			printf("%d   ", s[i].w);
		printf("\n");
		*/
		kruscal(n);
		printf("%d\n", sum + min);
		/*
		printf("----------------------------\n");
		for(i = 0; i < l; i++)
		{
			printf("%d - %d = %d\n", s[i].x, s[i].y, s[i].w);
		}
		*/
	}
	return 0;
}