讨论 / 错哪儿?
996760929 2011-11-05 08:19:00
点我顶贴 收藏 删除
const

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.

#1 996760929@2009-01-17 18:33:00
回复 删除
prim

#2 why19931123@2009-01-18 19:17:00
回复 删除
第18行:

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.

#3 hades@2009-02-27 01:43:00
回复 删除
晾程序喽

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.

#4 wa__123@2010-08-10 02:17:00
回复 删除
晒程序 并查集做的

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.

#5 mlz000@2011-11-05 08:19:00
回复 删除
求解释额,为啥不过额

#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;

}

查看更多回复
提交回复