手一抖看错了数据范围。。。

题目没看懂。。。
“第二行为这种排列方案下的一个人的期望等待时间(输出结果精确到小数点后两位)”
我觉得我语文白学了
好像是。。。每个人平均等待时间的意思

NOIp2013压线，这题win下报0，linux下AC，很奇怪

用的Prim+邻接表+二叉堆。。超时2个点。
邻接表改邻接矩阵，全过了==
总时间Kruskal比Prim快0.5s左右。

研究了一下Kruskal。
用了一种效率很低的【不相交集合】处理的方法处理的。但是竟然还是那么快，堪比二叉堆+Prim，这。。。
下面给上效率较高[路径压缩]的并查集的Kruskal的写法。[可用按秩合并或路径压缩的启发式策略来优化]

/*

/*

DESIGNED BY CH

KRUSKAL+UFS

ON 2013/12/5 23:06

*/

#include<fstream>

#include<vector>

#include<algorithm>

using namespace std;

ifstream fi("agrinet.in");

ofstream fo("agrinet.out");

const int INF=0xffffff;

const int Len=100+10;

int A[Len][Len],F[Len],n;

vector<pair<int,pair<int,int> > >E;

void init();

void Kruskal();

void Uion(int,int);

int Find(int);

int main()

{

 init();

 Kruskal();

 return 0;

}

void init(){int i,j;

 fi>>n;

 for(i=0;i<n;i++)for(j=0;j<n;j++)fi>>A[i][j];

 for(i=0;i<n;i++)A[i][i]=INF,F[i]=i;

 for(i=0;i<n;i++)for(j=0;j<i;j++)E.push_back(make_pair(A[i][j],make_pair(i,j)));

}

void Kruskal()

{

 int Ans=0,sum=0,pos_S,pos_E;

 sort(E.begin(),E.end());

 while(sum<E.size())

 {

 pos_S=E[sum].second.first;pos_E=E[sum].second.second;

 if(Find(pos_S)!=Find(pos_E)){

 Ans+=A[pos_S][pos_E];

 Uion(pos_S,pos_E);

 }

 sum++;

 }

 fo<<Ans;

}

void Uion(int x,int y){

 F[Find(x)]=Find(y);

}

int Find(int x){

 return F[x]==x?x:F[x]=Find(F[x]);

}

粘模板真是风一样的爽感= =
学习@陈浩 ，给题加图

大数据都过了，为什么第二组超时，在我电脑上用时间函数表计算没超啊。
奇怪。。经检验写的代码在某些情况下会出现死循环，为什么在我电脑上过了==

class强迫症没治了= =

输入文件中string居然有\n 需要while(cin>>str)s+=str;坑！

回复 @cstdio :
这个解题过程太酷炫了

我有一个证明，但这里空白太小，写不下

受益匪浅

快排~

MST。介绍一下Prim吧。
根据题意，也不难理解什么是MST。
首先，MST具备以下2条重要的性质：
1.最优子结构；W(T)=W((u,v))+W(T1)+W(T2);(T1,T2为两棵子树，而(u,v)为连接这两棵树的边，即你切断的那条边)
2.重叠子结构；(最终均可化简至有限的相同的基本问题)
看似可以DP，但是，对于MST，不难发现还具备这条性质(其实是一个简单的定理)：
若将图G(V,E)化成2个部分，A和G-A，则若存在边(u,v)∈E使得A与G-A联通，则E(Min)∈MST.
这条定理告诉我们MST具备“局部最优解同时也是全局最优解“的属性；
而具备该属性则说明存在某种贪心策略可以生成MST。
Prim算法就是用到了这条定理来完成的。其实它和迪杰斯特拉很像。对于邻接表储存的稀疏图，加上二叉堆后可大大提高算法的速度。
当然，用斐波那契堆优化可达到极为拔群的效果。

已吓傻……为何突然冒出来这么多……

回复 @Strawberry :
ORZ

直接动规，果断慢成翔

我会写网络流了哈哈

回复 @cstdio :
小号旺。。。

喵的又跪在忘开long long上了……