门票

admin管理员组

文章数量:1122849

门票

【题目描述】
省运会准备进行开幕式门票的销售，假设售票点前聚集了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;
varf,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 beginmax:=maxlongint;for j:=1 to n doif (f[j]<max)and(b[j]=0) then beginmax:=f[j];u:=j;end;b[u]:=1;ans:=ans+f[u];for j:=1 to n doif map[u,j]<f[j] then f[j]:=map[u,j];end;write(ans);
end.

本文标签： 门票