有

http://wenku.baidu.com/link?url=S6wZXbSyKzMe7FGpJ26nHobJOBARHiNj8jVqPSZAeNuwaR8MMRj59J7r2aQKIwydHC7Oxhw85zKOpUi81vy6h1HrVCqrZv1JjXt-RzmQz5O
分治算法

莫名其妙的6个点E了（自己跑的时候没问题），然后什么都没改又交了几次莫名其妙的A了，表示彻底凌乱了。

这个题的名字为什么这么叼

拿了这道题的两次一血- -

两个看不见的时候必定可以找到两条平行切线，使两牛在平行线中
把所有切线的斜率求出来，然后排序，上平衡树扫描
求神犇，有没有不这么丧心病狂简单些的解法？

一开始find()函数完全打错了竟然还能对8个，难道那8个根本用不到find()么。。。

一个悲伤的故事：考场花了好长时间写得线段树，题目看错了。。。。

scanf读入后两点爆了，丧心病狂。
学习了是

%llu

不是

%ull

很赞的原创图片。From CH

google翻译
小妖精[从BOI'98通过， 2008]
试想一下，贝茜的惊喜，因为她窥探一个妖精通过北牧场腾跃。因为没有人的傻瓜，她被控在妖精的抓住了他与她的抓握蹄子。
“一个心愿，牛之一。这就是我对牛， ”他说。
“财富”贝西朦胧地说。 “有机会的财富。 ”
妖精从来没有授予正是他们的俘虏的愿望最简单的形式。从一个响亮的爆炸位置硝烟散尽，一个闪闪发光的甜甜圈慢慢旋涂在青翠的绿色田野。
“我已经给你做了圆环， ”妖精叫唤。 “而在该圆环是一个N× N矩阵（ 1 < = N < = 200 ）的整数，范围
-1,000,000 1,000,000 ..这将决定您的幅度
财富。你必须找到连续的整数序列中的所有
一行，一列，或者在一个对角线的收益率从上环面所有可能的序列中最大的一笔。 “
贝西沉吟了一会儿，意识到圆环是一个设备为“包装”的列，行和矩阵的对角线，这样人们可以选择连续的元素， “缠”的侧面或顶部边缘。
贝茜将与您分享矩阵。确定的值
最大可能的总和（这要求选择的至少一个矩阵元素）。
通过举例的方式，考虑4×4矩阵的左侧下方具有从一个示例性的“包装”对角线标注的所有元素：
8 6 6 * 1 8 6 * 6 1
-3 4 0 5 * -3 4 0 5
4 * 2 1 9 4 2 1 9 *
1 -9 * 9 -2 1 -9 9 * -2
标记对角线右侧矩阵包括两个九
（可用的最高数）和一个6为总共24 。这
是最佳的总和为这个矩阵和仅包括3
在其对角线上的四个可能的因素。
题目名称： LEPR
输入格式：
*第1行：一个整数：不适用
*第2 .. N +1行：第i +1行包含N个用空格隔开的整数的
构成第i行的矩阵
输入样例（文件lepr.in ） ：
4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2
输出格式：
*第1行：一个整数，它是最大可能的总和可计算
使用上面的规则
输出样本（文件lepr.out ） ：
24

涨姿势了。。。原来题还可以这样写。。。

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

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

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强迫症没治了= =