第一遍连KRUSKAL都写错了...

这道题交了无数遍，看了不少题解没看懂

我自己总结了：

1.第一遍kur求出最小生成树

2.次优解就是把求出来的n-1条边依删除（并查集删除不会自己查），分成两块不联通的图，枚举m条边（每次求出第一条满足条件的边后就break）

3.最后答案更新时注意细节

4.数组

5.rp

两遍。。

第一遍M的范围开小了。。。。郁闷

难度不大，不想追求很少时间的话很容易，但注意－1前面也要加Cost:

KRUSKAL+并查集，核心代码如下：

function find(x:longint):longint;

begin

if father[x]x then exit (find(father[x]))

else exit (x);

end;

procedure union(x:longint);

begin

if father[x]x then

begin

union(father[x]);

father[x]:=dad;

end

else father[x]:=dad;

end;

procedure kur;

var

q,i:integer;

begin

q:=1; i:=1;

while q

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

数组开25000。。。。。WAR 3 次

改250000 过了。。。。。。。。。。。。。。。。。。。

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 525ms

├ 测试数据 05：答案正确... 525ms

├ 测试数据 06：答案正确... 509ms

├ 测试数据 07：答案正确... 509ms

├ 测试数据 08：答案正确... 541ms

├ 测试数据 09：答案正确... 697ms

├ 测试数据 10：答案正确... 759ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4065ms

俺地神哪，我尽力了……

我用的是prim找到最小树，然后穷举断开最小树里面的边，再prim算法n-1次。在再次调用prim时凡是已产生的边的权之和已经大于当前求得的最有解就跳出prim过程。结果还是这么慢……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

无语

这题花了我2个多小时……

第一次交WA，Qsort的swap错了

第二次交WA，没用longint

请问 如何 break

失误性的把并查集打错了。。。WA了5次。。

100MS+..速度不错..

如果再加个break可能更好..

无语了…………

因为复制的问题wa了N次，我的通过率啊！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 119ms

├ 测试数据 08：答案正确... 369ms

├ 测试数据 09：答案正确... 462ms

├ 测试数据 10：答案正确... 603ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1603ms

尽管过了，但是第一组答案竟然是负数，这是为什么？

弟兄们，第四组数据超了int范围(longint)

多加注意...

编译通过...

├ 测试数据 01：答案正确... 41ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 56ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：328ms

不难。。主要用到KRUSKAL。

枚举边来删除。

还有，每一次删边记得还原FATHER[]节点！

当T》M时BREAK； 不更新ANS。！！

Kruskal　记得Break，还有数组开到10W

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：185ms

bs输出。。大写，还得wa了两次。。

次小生成树。。kruskal+并查集。。依次删边

极度BS ipip2005的算法,样例都过不了

浪费了我1.5小时 5555555555~~~~~~~~~

真后悔没早看见332404521的话

第一步：先求一次prim，比一般prim要多做的就是记录最小生成树的所以边

第二步：把这些边依次去掉。

因为最小生成树两点间有切仅有一条路径，所以该次去除使原图变成了

两个不相连的生成树，枚举两个块中的点对，取距离最小的一对，那么这次操作

的答案就是最优解ans1-去掉的路径长+求出的最小距离

优化`就是第一次求最小的时候记录找了哪些边。以后循环的时候只需要把这些边枚举去掉就行``