【题目描述】 省运会准备进行开幕式门票的销售，假设售票点前聚集了N个人购买门票。有M组出现第X个人帮助第Y个人买票(X可以等于Y，此时第X个人可以给自己买票)，这时消耗时间W[X,Y]（1<=W[x,y]<=20000）。 当然，这种帮助是相互的，也就是说如果第Y个人帮助第X个人买票，也将花费W[X,Y]个单位时间。 注意： 1.每个人帮助别人买票的时候必须要求自己已经购得开幕式门票。 2.X帮Y买票的时间有可能多次出现，必须从中选择较小的。 求解这N个人购买票的最短时间和，对于每个数据都保证N个人都获得开幕式门票。 【输入格式】 第一行两个正整数分别为N,M 以后M行，每行三个正整数X,Y,W[X,Y] 【输出格式】 一行一个整数，为N个人都购得开幕式门票的最短时间 【样例输入】 3 5 1 1 5 2 2 2 2 1 4 3 3 3 3 2 6 【样例输出】 9 【数据范围】 N<=2000,M<=13000 【分析】 Prim算法做最小生成树。
uses math; var f,b:array[0..2001]of longint; map:array[0..2001,0..2001]of longint; n,i,m,max,u,j,ans:longint; begin readln(n,m); fillchar(map,sizeof(map),$7f); for u:=1 to m do begin readln(i,j,ans); map[i,j]:=min(ans,map[i,j]); map[j,i]:=map[i,j]; end; for i:=1 to n do f[i]:=map[i,i]; ans:=0; fillchar(b,sizeof(b),0); for i:=1 to n do begin max:=maxlongint; for j:=1 to n do if (f[j]<max)and(b[j]=0) then begin max:=f[j]; u:=j; end; b[u]:=1; ans:=ans+f[u]; for j:=1 to n do if map[u,j]<f[j] then f[j]:=map[u,j]; end; write(ans); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533495.html
