Kruskal+并查集+路径压缩

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

a,b,c:array[1..10000] of longint;

fa:array[1..1000] of longint;

n,m,k,i,t,j1,j2,tot,ans:longint;

procedure qsort(bot,top:longint);

var

x,y,mid,swap:longint;

begin

x:=bot;y:=top;mid:=c[(x+y) div 2];

repeat

while c[x]mid do y:=y-1;

if xy;

if xc[j]) then

begin

min:=c[j];

p:=b[j];q:=j;

end;

end;

end;

begin

init;

fillchar(use,sizeof(use),false);

fillchar(ok,sizeof(ok),false);

use[1]:=true;

for i:=1 to n-1 do

begin

min:=maxlongint;

p:=0;

find;

if min=maxlongint then

begin

writeln('No Answer');

halt;

end;

ans:=ans+min;

use[p]:=true;

ok[q]:=true;

end;

for i:=1 to k-1 do

begin

p:=0;max:=0;

for j:=1 to m do

if (ok[j])and(c[j]>max) then

begin

max:=c[j];

p:=j;

end;

ans:=ans-max;

ok[p]:=false;

end;

writeln(ans);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var u,v,len:array[1..10000] of longint;

f:array[1..1000] of longint;

n,m,k,i,j,tot:longint;

function find(x:longint):longint;

begin

if f[x]x then f[x]:=find(f[x]);

exit(f[x]);

end;

procedure qsort(l,r:longint);

var ii,jj,x,t:longint;

begin

ii:=l;

jj:=r;

x:=len[(l+r) div 2];

repeat

while len[ii]x do dec(jj);

if iijj;

if iil then qsort(l,jj);

end;

begin

readln(n,m,k);

for i:=1 to m do

readln(u[i],v[i],len[i]);

for i:=1 to n do

f[i]:=i;

j:=1;

qsort(1,m);

if k>n then

begin

writeln('No Answer');

halt;

end;

for i:=1 to n-k do

begin

while (find(u[j])=find(v[j]))and(j

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

并查集+kruska

总而言之，言而总之，是冰茶不熟啊

#include

using namespace std;

int a[1001],n,m,k;

struct SPTREE

{

int v1,v2;

int edge;

};

struct SPTREE b[10001];

int Comp(const void *p1,const void p2 )

{

return ((struct SPTREE )p1).edge > ((struct SPTREE *)p2).edge ? 1 : -1;

}

void union1(int r1, int r2)

{

if(a[r2]>b[i].edge;

qsort(b,m,sizeof(b[0]),Comp);

}

int main(void)

{

init();

work111();

return 0;

}

又一次AC了，kruskal越练越熟手了。。。

PRIN的话写得很奇怪。。。。

HINT:终于在提交之前用自测数据改成了AC程序

如果不能秒杀的话就是RP问题了^_^

一次AC kruskal n-k条边

想不出这道题用PRIM怎么做~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

kruskal n-k条边

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Easy Kruskal

并查集其实挺好用的！！！

秒杀！！！！！！！！！！！！！

哈哈！！！！！！！！！！！！！！！

！！！！！！！！！！！！！！！！！！！

！！！！！！！！！！！！！！！！！！！！

！！！！！！！！！！！！！！！！！！！！！

！！！！！！！！！！！！！！！！！！！！！！！

！！！！！！！！！！！！！！！！！！！！！！！！！

！！！！！！！！！！！！！！！！！！！！！！！！！！！

！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

prim也能过

核心部分：

while r

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

根本不用并查集，不用贪心

死活秒杀了它

总算AC 一个中午啊

发现并查集也挺好用的，写熟了就好 这次的收获

1.sort(1,n)是不可以的,要sort(1,m) 还有数组开到1..maxm 不要开到1..maxn 要仔细

2.sort 的时候，有个技巧，二维数组可以a[0]:=a[1]，这样就不用写三次了

3.非常重要的是 father[v]:=getfather(father[v]) ， 不是getfather(v) 这种错误，考试的时候要出来的，就怎么都改不了了

4.这个和一般的最小生成树的并查集写法有点区别

最后，自己编数据，开随机，提高AC率！！

Kruscal超炫！

用readln之前，10个点全‘选手答案比标准输出长’，用readln后，AC！

错误答案全是负数！

结果发现原来打算在写完程序以后把所有的integer换成longint的！ 结果忘了！ 日日日 白浪费一次AC率。

用PRIM 的注意!!!

两点之间有多条不同的边,要存最短的........调了我好久.....

细节决定成败啊..

快排漏了=号...

切记切记....

并查+快排+贪心+(细心)=AC!

很多人不理解为什么是构造n-k条边，我来讲讲吧,我们知道,给定N个点,那么最小生成树便有N-1条边.根据题目我们可以知道,棉花糖可以由一个云构成,而构造这样一个由一个云组成的棉花糖是不费费用的。所以,我们要构造的就是一个n-1-(k-1)的最小生成树,现在大家都清楚了吧?

P.S.我以口袋一样的姿势提交了口袋一样的代码挂着口袋一样的表情看到了口袋一样的"Accepted"

竟然写成qsort（1，n），无语啊