好久没做最小生成题了，只记得算法。。。快比赛了突然在这又出了问题
prim算法要用邻接矩阵适用于顶点少的题，做题习惯直接把这种用矩阵的先给排除了，直接用vector，结构体，导致一道题会用时很久
做题可不能像我这样，看到题要知道用什么算法，还要去想下需要用哪种数据结构（当算法比较多的时候，我们就要考虑题中的数据，根据题中给的数据大小选择数据结构，继而在选择这个算法的哪种）‘
因为顶点不多，就用了prim算法，用了krus（）但是runtime了。。。不想再改了~
#include<stdio.h> #include<string.h> #include<algorithm> #define inf 0x3f3f3f using namespace std; int n,m; int map[505][505]; int dis[505]; int vis[505]; int prim() { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); int i,count=0,u,v,sum=0; for(i=1;i<=n;i++) { dis[i]=map[1][i]; } vis[1]=1; count++; while(count<n) { int min=inf; for(i=1;i<=n;i++) { if(!vis[i]&&dis[i]<min) { min=dis[i]; u=i; } } vis[u]=1; sum+=dis[u]; count++; for(v=1;v<=n;v++) { if(!vis[v] && dis[v]>map[u][v]) { dis[v]=map[u][v]; } } } return sum; } int main() { int T; scanf("%d",&T); while(T--) { memset(map,0x3f,sizeof(map)); int i,u,v,w; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) map[i][i]=0; for(i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); map[u][v]=map[v][u]=w; } int min=1<<28; for(i=0;i<n;i++) { scanf("%d",&u); if(min>u) { min=u; } } min+=prim(); printf("%d\n",min); } return 0; }