安慰奶牛 问题描述 Farmer John变得非常懒，他不想再继续维

时间：2021-03-06 04:42:02
package ALGO;

/*安慰奶牛  
 时间限制：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。*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

//Kruskal最小生成树

class Cow implements Comparable<Cow> {

	int u;
	int v;
	int w;

	public Cow(int u, int v, int w) {
		this.u = u;
		this.v = v;
		this.w = w;
	}

	// 为了更快，自定义排序方法
	public int compareTo(Cow o) {
		return w > o.w ? 1 : -1;
	}
}

public class AnweiCow {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] order = br.readLine().split(" ");
		int n = Integer.parseInt(order[0]);
		int p = Integer.parseInt(order[1]);

		int[] anweitime = new int[n];
		int mintime = Integer.MAX_VALUE;// 记录出需要安慰最少时间的奶牛的安慰时间
		for (int i = 0; i < anweitime.length; i++) {
			int time = Integer.parseInt(br.readLine());
			if (time < mintime)
				mintime = time;
			anweitime[i] = time;
		}

		// 一个存放顶点的集合
		ArrayList<Cow> list = new ArrayList<Cow>();
		for (int i = 0; i < p; i++) {
			String data[] = br.readLine().split(" ");
			int u = Integer.parseInt(data[0]);
			int v = Integer.parseInt(data[1]);
			int w = Integer.parseInt(data[2]);
			list.add(new Cow(u, v, w * 2 + anweitime[u - 1] + anweitime[v - 1]));
		}

		Collections.sort(list);

		int alltime = 0;
		// 在这实现克鲁斯卡尔算法，求最小生成树
		int[] lowcost = new int[n + 1];
		for (int i = 0; i < p; i++) {

			int a = find(lowcost, list.get(i).u);
			int b = find(lowcost, list.get(i).v);

			if (a < b) {
				lowcost[b] = a;
				alltime += list.get(i).w;
			} else if (a > b) {
				lowcost[a] = b;
				alltime += list.get(i).w;
			}
		}
		System.out.println(alltime + mintime);
	}

	// 通过lowcost数组和这个find的方法，来检查是否行程环路
	public static int find(int[] lowcost, int k) {

		while (lowcost[k] > 0) {
			k = lowcost[k];
		}
		return k;
	}
}

标签：

相关文章