d[v[i]]=d[x]+w[i]; if(!inq[v[i]]) {

inq[v[i]]=true; (v[i]); } } }

编号：ALGO-6 题目：安慰奶牛 关键字：最小生成树 类型：普通试题 问题描述

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。 本题的Java参考代码如下： import Reader3{

static BufferedReader reader;

static StringTokenizer tokenizer;

static void init(InputStream input){

reader=new BufferedReader(new InputStreamReader(input)); tokenizer=new StringTokenizer(\ }

static String next() throws IOException{ while (!()) {

tokenizer = new StringTokenizer( )); }

return (); }

static int nextInt() throws IOException{ return (next()); }

static double nextDouble() throws IOException{ return (next()); } }

class KruskalDui{ int a,b,l; }

public class Main{ /**

* @param args

* @throws IOException */

static int father[]=new int[100000];

static ArrayList path =new ArrayList();

public static int getfather(int x) { if (x!=father[x]) {

father[x]=getfather(father[x]); }

return father[x]; }

public static void _qst_w(int l,int r) { int i=l,j=r,mw=((i+j)/2).l; while(i<=j){

while(i).lmw) j--; if(i<=j){ (path,i,j); i++;j--; } }

if(l

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

fy=getfather(k).b); if(fx!=fy){ father[fx]=fy; result+=(k).l; count++; } k++; } } }

编号：ALGO-7 题目：逆序对 关键字：平衡二叉树 类型：普通试题 问题描述

Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：

有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a[1]…a[n]。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。

Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。