我用 prim过了 kruskal 0分
#include<stdio.h>
int map[500][500]; //a linking map
int edges[30][3]; //[0][0] is the flag of going through
struct { int parent; } collec[40]={0};//[0] is the number of symbols
int P,E; //points and edges
int total=0;
void edgesort(int edges[][3],int fir,int las)
{
int bas=edges[fir][0];
int i=fir; int j=las;
int temp1,temp2;
temp1=edges[fir][1];
temp2=edges[fir][2];
while(i<j)
{
while((edges[j][0]>=bas)&&(i<j)) j--;
edges[i][0]=edges[j][0];
edges[i][1]=edges[j][1];
edges[i][2]=edges[j][2];
while((edges[i][0]<=bas)&&(i<j)) i++;
edges[j][0]=edges[i][0];
edges[j][1]=edges[i][1];
edges[j][2]=edges[i][2];
}
edges[i][0]=bas;
edges[i][1]=temp1;
edges[i][2]=temp2;
if(fir<i) edgesort(edges,fir,i-1);
if(i<las) edgesort(edges,i+1,las);
}
int in(int p1,int p2) /// return 1 tells that the symbool is in the same collection
{
int root1,root2;
root1=p1;root2=p2;
while(collec[root1].parent!=-1) root1=collec[root1].parent;
while(collec[root2].parent!=-1) root2=collec[root2].parent;
if(root1==root2) return 1;
else return 0;
}
void link(int p1,int p2)
{
int root1,root2;
root1=p1;root2=p2;
while(collec[root1].parent!=-1) root1=collec[root1].parent;
while(collec[root2].parent!=-1) root2=collec[root2].parent;
collec[root2].parent=root1;
}
void krus(int root)
{
int i,j,flag;
for(i=1;i<=P;i++) collec[i].parent=-1;
edges[0][0]=1;
edgesort(edges,1,E);
for(j=1;j<=P-1;j++)
{
while( in( edges[edges[0][0]][1],edges[edges[0][0]][2] )==1) edges[0][0]++;
link(edges[edges[0][0]][1],edges[edges[0][0]][2]);
total+=edges[edges[0][0]][0];
}
}
int main()
{
int i,j;
int tot=0;
scanf("%d%d",&P,&E);
for(i=1;i<=E;i++)
{
scanf("%d%d%d",&edges[i][1],&edges[i][2],&edges[i][0]);
map[edges[i][1]][edges[i][2]]=edges[i][0];
map[edges[i][2]][edges[i][1]]=edges[i][0];
tot+=edges[i][0];
}
krus(1);
printf("%d",tot-total);
return 0;
}
program t370;
var
f:longint;
n,k,c,b,d,e:integer;
a:array[1..3,1..10000]of integer;
qq:array[1..100]of boolean;
fa:array[1..100]of integer;
function gf(v:integer):integer;
begin
if fa[v]=0 then gf:=v
else
begin
fa[v]:=gf(fa[v]);
gf:=fa[v];
end;
end;
procedure kp(l,r:integer);
var
i,j,x1,x2,x3,a1,a2,a3,q:integer;
begin
q:=(l+r) div 2;
i:=l;j:=r;
x3:=a[3,q];
repeat
while (x3>a[3,i])do inc(i);
while (x3<a[3,j])do dec(j);
if not(i>j) then
begin
a1:=a[1,j];a2:=a[2,j];a3:=a[3,j];
a[1,j]:=a[1,i];a[2,j]:=a[2,i];a[3,j]:=a[3,i];
a[1,i]:=a1;a[2,i]:=a2;a[3,i]:=a3;
inc(i);
dec(j);
end;
until i>j;
if i<r then kp(i,r);
if l<j then kp(l,j);
end;
begin
f:=0;
readln(n,k); c:=0;
for b:=1 to n do begin qq[b]:=false;fa[b]:=0;end;
for b:=1 to k do
begin
inc(c);
readln(a[1,c],a[2,c],a[3,c]);
end;
kp(1,n);
for b:=1 to k do
begin
c:=gf(a[1,b]);
d:=gf(a[2,b]);
if c<>d then begin qq[b]:=true;fa[d]:=c;end;
end;
for b:=1 to n do
if not qq[b] then f:=f+a[3,b];
write(f);
end.
program t370;
var
f:longint;
n,k,c,b,d,e:integer;
a:array[1..3,1..10000]of integer;
qq:array[1..100]of boolean;
fa:array[1..100]of integer;
function gf(v:integer):integer;
begin
if fa[v]=0 then gf:=v
else
begin
fa[v]:=gf(fa[v]);
gf:=fa[v];
end;
end;
procedure kp(l,r:integer);
var
i,j,x1,x2,x3,a1,a2,a3,q:integer;
begin
q:=(l+r) div 2;
i:=l;j:=r;
x3:=a[3,q];
repeat
while (x3>a[3,i])do inc(i);
while (x3<a[3,j])do dec(j);
if not(i>j) then
begin
a1:=a[1,j];a2:=a[2,j];a3:=a[3,j];
a[1,j]:=a[1,i];a[2,j]:=a[2,i];a[3,j]:=a[3,i];
a[1,i]:=a1;a[2,i]:=a2;a[3,i]:=a3;
inc(i);
dec(j);
end;
until i>j;
if i<r then kp(i,r);
if l<j then kp(l,j);
end;
begin
f:=0;
readln(n,k); c:=0;
for b:=1 to n do begin qq[b]:=false;fa[b]:=0;end;
for b:=1 to k do
begin
inc(c);
readln(a[1,c],a[2,c],a[3,c]);
end;
kp(1,n);
for b:=1 to k do
begin
c:=gf(a[1,b]);
d:=gf(a[2,b]);
if c<>d then begin qq[b]:=true;fa[d]:=c;end;
end;
for b:=1 to n do
if not qq[b] then f:=f+a[3,b];
write(f);
end.
program t370;
var
f:longint;
n,k,c,b,d,e:integer;
a:array[1..3,1..10000]of integer;
qq:array[1..10000]of boolean;
fa:array[1..100]of integer;
function gf(v:integer):integer;
begin
if fa[v]=0 then gf:=v
else
begin
fa[v]:=gf(fa[v]);
gf:=fa[v];
end;
end;
procedure kp(l,r:integer);
var
i,j,x1,x2,x3,a1,a2,a3,q:integer;
begin
q:=(l+r) div 2;
i:=l;j:=r;
x3:=a[3,q];
repeat
while (x3>a[3,i])do inc(i);
while (x3<a[3,j])do dec(j);
if not(i>j) then
begin
a1:=a[1,j];a2:=a[2,j];a3:=a[3,j];
a[1,j]:=a[1,i];a[2,j]:=a[2,i];a[3,j]:=a[3,i];
a[1,i]:=a1;a[2,i]:=a2;a[3,i]:=a3;
inc(i);
dec(j);
end;
until i>j;
if i<r then kp(i,r);
if l<j then kp(l,j);
end;
begin
f:=0;
readln(n,k); c:=0;
for b:=1 to n do begin fa[b]:=0;end;
for b:=1 to k do
begin
qq[b]:=false;
inc(c);
readln(a[1,c],a[2,c],a[3,c]);
end;
kp(1,n);
for b:=1 to k do
begin
c:=gf(a[1,b]);
d:=gf(a[2,b]);
if c<>d then begin qq[b]:=true;fa[d]:=c;end;
end;
for b:=1 to k do
if not qq[b] then f:=f+a[3,b];
write(f);
end.
改一下就可以了
一次AC
#include"stdio.h"
typedef struct
{
long b,e,v;
}NET;
NET net[120];
long n,m;
long used[120];
void qsort(long ss,long ee)
{
long c=ss,d=ee,xx=net[(ss+ee)/2].v;
NET temp;
do
{
while(net[c].v<xx) c++;
while(net[d].v>xx) d--;
if(c<=d)
{
temp=net[c]; net[c]=net[d]; net[d]=temp;
c++;
d--;
}
}while(c<=d);
if(d>ss) qsort(ss,d);
if(c<ee) qsort(c,ee);
}
long getf(long x)
{
if(used[x]==x) return x;
used[x]=getf(used[x]);
return used[x];
}
int main()
{
long ans=0;
scanf("%ld%ld",&n,&m);
for(long i=1;i<=m;i++)
scanf("%ld%ld%ld",&net[i].b,&net[i].e,&net[i].v);
for(long i=1;i<=119;i++)
used[i]=i;
qsort(1,m);
for(long i=1;i<=m;i++)
{
if(getf(used[net[i].b])!=getf(used[net[i].e]))
used[getf(net[i].e)]=used[getf(net[i].b)];
else ans+=net[i].v;
}
printf("%ld",ans);
getchar(),getchar();
return 0;
}