编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

狂顶prim+堆优化＋邻接表

注意堆中储存节点的编号，而不是到生成树的距离，不然太麻烦了；

以到生成树的距离维护堆；

推荐模块化操作

请问第十个点到底是什么? 我交了无数次 还是第十个点WA了、

#include

#include

#include

#include

#include

#define MAXN 200001

#define MAXM 200001

using namespace std;

double S , cost[MAXN] , Length ;

int cnt = 0 , now[MAXN] , pre[MAXN] , M , N ;

int U[MAXN] , V[MAXN] ;

int father[MAXN] , Cnt = 0 ;

bool visit[MAXN] ;

void QuickSort(int l , int r)

{

int i = l , j = r ;

double Mid = cost[( l + r ) >> 1] ;

while (i Mid) j--;

if (i l) QuickSort(l,j);

}

int Getfather(int u)

{

if (father == u) return u ;

father = Getfather(father);

return father ;

}

void Kruskal()

{

for (int i = 1 ; i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

{提醒大家一下,最后一个点要当心!}

刷了9次才过..........

我可怜的正确率呀...........

Qsort+Kruscal+并查集

var i,j,n,m,x,y:longint;

s,s0:real;

v,u,fa:array[1..100000] of longint;

a:array[1..100000] of real;

b:boolean;

function find(x:longint):longint;

begin

if fa[x]=x then find:=x

else

begin

find:=find(fa[x]);

fa[x]:=find;

end;

end;

procedure qsort(s,t:longint);

var i,j,t1:longint;

x,t0:real;

begin

x:=a;

i:=s;

j:=t;

repeat

while (a[i]x) do dec(j);

if ij;

if s

#include

#include

#include

#include

#include

#include

using namespace std;

#define MS(s) memset(s,0,sizeof(s))

#define E 999999999

int n,m;

double ans=0.0,s;

int fa[200000];

struct edge{

int x,y;

double weight;

} e[200000];

int cmp(edge a,edge b) {

return a.weight>s >>n;

int a,b;

double f;

while( (scanf("%d%d%lf",&a,&b,&f))!=-1 ) {

++m;

e[m].x=a;

e[m].y=b;

e[m].weight=f;

}

if(m

标准Kruscal练手

注意下图可能不连通

没有秒杀 哎

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

并查集+KURSKAL+QSORT很好很强大，虐杀稀疏图

并查集 瞬秒

type

re=record

be,en:longint;

quan:real;

end;

arr=array[1..100000] of re;

var

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

a:arr;

i,x,y,k,b,n,m,p,nn:longint;

sum,s:real;

function father(w:longint):longint;

begin

if fa[w]=w then father:=w else begin fa[w]:=father(fa[w]);father:=fa[w];end;

end;

procedure union(a,b:longint;data:real);

begin

x:=father(a);y:=father(b);

if xy then begin inc(nn);sum:=sum+data;fa[x]:=y;end;

end;

procedure quicksort(var b:arr; s,t:longint);

var i,j:longint;

x:real;

t1:re;

begin

i:=s;j:=t;x:=b[i].quan;

repeat

while (b[j].quan>=x) and (j>i) do j:=j-1;

if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;

while (b[i].quan

那位 大牛帮忙看看？？？

////////////////////////

type rec=record

x,y:longint;

len:real;

end;

var a:array[-1..1000000] of rec;

f:array[-1..1000000] of longint;

n,p,i,j,k,l,fx,fy:longint;

s,ans:real;

aa:rec;

procedure qsort(l,r:longint);

var i,j:longint;

x:real;

y:rec;

begin

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

i:=l;j:=r;

repeat

while a[i].lenx do dec(j);

if ij;

if i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

随机化快排+Kruskal+并查集=AC

还有一点：要注意m

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

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

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

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

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

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

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

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

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

├ 测试数据 10：答案错误...程序输出比正确答案长

看了下面的才知道是因为有可能无法连通

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Qsort+Kruskal+并查集+Evolution Smdcn = 72ms

注意readln否则**RuntimeError106**

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

稀疏图prim果然比较慢。。。

** 会写并查集后感觉 kruskal 还是蛮好写的... **

50分的看下。

这里判断getfather(x)getfather(y)后，是fa[fa[x]]:=fa[y]

我写成fa[x]:=fa[y]了....看了一个小时....

可恶的细节啊！我的AC率。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

囧，现在才知道并查集还有路径压缩这东西，我真的是落伍了……

最小生成树

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

kruscal...

program p1045;

var x,y,fa:array[0..200001] of longint;

w:array[0..200001] of extended;

i,j,k,l,m,n,p,q,r:longint;

sum,min:extended;

procedure qsort(i,j:longint);

var s,l,r:longint;

g,t:extended;

begin

t:=w[(i+j) div 2];l:=i;r:=j;

repeat while w[l]t do dec(r);

if lr;

if l

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program P1045;

var n,i,m,k:longint;

s,min:real;

flag:boolean;

x,y,f:array [-1..1000000] of longint;

ss:array [-1..1000000] of real;

function find(x1:longint):longint;

begin

if f[x1]=x1 then find:=x1

else find:=find(f[x1]);

f[x1]:=find;

end;

function pd(a,b:longint):boolean;

begin

if find(a)=find(b) then pd:=false

else pd:=true;

end;

procedure hb(a,b,i:longint);

begin

if pd(a,b) then begin

f[find(a)]:=find(b);

min:=min+ss[i];

inc(k);

end;

end;

procedure swap(var a,b:longint);

var t1:longint; t2:real;

begin

t1:=x[a]; x[a]:=x; x:=t1;

t1:=y[a]; y[a]:=y; y:=t1;

t2:=ss[a]; ss[a]:=ss; ss:=t2;

inc(a); dec(b);

end;

procedure qsort(l,r:longint);

var i1,j1:longint; x:real;

begin

i1:=l;j1:=r;x:=ss[l];

repeat

while ss[i1]