d=1000;
var
a:array[1..100,1..100]of longint;
s:array[1..100]of boolean;
p:array[1..100]of longint;
i,j,t,k,q,u,r,n,m,c:longint;
d1,d2:longint;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=d;
r:=0;
for i:=1 to m do
begin
readln(d1,d2,a[d1,d2]);
if a[d1,d2]<>0 then begin a[d1,d2]:=a[d2,d1];end;
inc(r,c);
end;
fillchar(s,sizeof(s),false);
s[1]:=true;
q:=0;
for i:=2 to n do
p[i]:=a[1,i];
for i:=2 to n do
begin
t:=d;
for j:=2 to n do
if not(s[j])and(p[j]<t) then begin
t:=p[j];
u:=j;
end;
s[u]:=true;
inc(q,t);
for j:=2 to n do
if not(s[j])and(a[u,j]<p[j]) then p[j]:=a[u,j];
end;
write(r-q);
end.
f a[d1,d2]<>0 then begin a[d1,d2]:=a[d2,d1];end;
改为:
f a[d1,d2]<>0 then begin a[d2,d1]:=a[d1,d2];end;
其他地方看不太懂!
给你看一下我的AC程序:
var
f:array[1..100,1..100]of longint;
s,m,n,o,p,q,r:longint;
procedure prim;
var
lowcost:array[1..100]of longint;
closest:array[1..100]of longint;
min,max,i,j,k:longint;
begin
for i:=1to m do
begin
lowcost[i]:=f[1,i];
closest[i]:=1;
end;
for i:=1to m-1do
begin
min:=2147483647;
for j:=1to m do
if(lowcost[j]<min)and(lowcost[j]<>0)
then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0;
for j:=1to m do
if f[k,j]<lowcost[j]
then begin
lowcost[j]:=f[k,j];
closest[j]:=k;
end;
end;
for i:=2to m do
r:=r-f[closest[i],i];
end;
begin
readln(m,n);
for o:=1to m do
for p:=1to m do
f[o,p]:=2147483647;
for o:=1to n do
begin
readln(p,q,s);
f[p,q]:=s;
f[q,p]:=s;
r:=r+s;
end;
prim;
write(r);
end.
program dffd;
var
n,m,l,k,j,d,t,i,min,tot:longint;
map:array[1..100,1..100] of integer;
procedure prim;
var
i,j,k,l,p:longint;
cost:array[1..100] of longint;
begin
for i:=1 to n do
cost[i]:=map[1,i];
cost[1]:=0;
for i:=2 to n do
begin
min:=maxint;
for j:=1 to n do
if (cost[j]<min)and(cost[j]<>0) then begin
min:=cost[j];
p:=j;
end;
tot:=tot+min;
cost[p]:=0;
for k:=1 to n do
if (cost[k]<>0) and (cost[k]>map[p,k]) then
cost[k]:=map[p,k];
end;
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do
map[i,j]:=maxint;
for i:=1 to m do
begin
readln(l,j,d);
map[l,j]:=d;
map[j,l]:=d;
t:=t+d;
end;
prim;
writeln(t-tot);
end.
var
n,m,ans,i,j0:longint;
x,y,t:Array[1..10009] of longint;
fa:array[1..10000] of longint;
function get(x:longint):longint;
begin
if fa[x]=x then exit(x);
fa[x]:=get(fa[x]);
exit(get(fa[x]));
end;
procedure sort(l,r:longint);
var
i,j,tt,xx:longint;
begin
i:=l; j:=r;
tt:=t[(i+R) div 2];
repeat
while t[i]<tt do inc(i);
while t[j]>tt do dec(j);
if not(i>j) then
begin
xx:=x[i]; x[i]:=x[j]; x[j]:=xx;
xx:=y[i]; y[i]:=y[j]; y[j]:=xx;
xx:=t[i]; t[i]:=t[j]; t[j]:=xx;
dec(j); inc(i);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure mercy(x,y:longint);
var xx,yy:longint;
begin
xx:=get(x);
yy:=get(y);
fa[xx]:=yy;
end;
begin
readln(n,m);
for i:=1 to n do fa[i]:=i;
for i:=1 to m do
readln(x[i],y[i],t[i]);
sort(1,m);
for i:=1 to m do
begin
if get(x[i])<>get(y[i]) then mercy(x[i],y[i]) else
inc(ans,t[i]);
end;
writeln(ans);
end.
#include<cstdio>//为啥不过?
#include<iostream>
#include<algorithm>
using namespace std;
const int N=10300;
int f[N];
struct arc
{
int x;
int y;
int w;
}edge[N];
bool cmp(const arc p,const arc &q)
{
return p.w<q.w;
}
int find(int x)
{
if(f[x]==x) return f[x];
else return f[x]=find(f[x]);
}
int main()
{
int i,j,k,n,ans=0,sum=0;
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i)
f[i]=i;
for(i=1;i<=k;++i)
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
sort(&edge[1],&edge[n+1],cmp);
for(i=1;i<=n;++i)
sum=sum+edge[i].w;
i=1;j=0;
while(j<n-1)
{
while(find(edge[i].x)==find(edge[i].y))
i++;
f[find(edge[i].x)]=find(edge[i].y);
ans=ans+edge[i].w;
j++;
}
ans=sum-ans;
printf("%d",ans);
// system("pause");
return 0;
}