题意： 给出n个节点，再有m条边，这m条边代表从a节点到b节点电缆的长度，现在要你将所有节点都连起来，并且使长度最短。 题解： 把所有点链接起来，还要最短，说明要用最小生成树，然后 因为是单边的，用prim时要把单边变成双边，即是无向图，但是用kruskal的话可以避免这种情况，因为kruskal是把边都从小到大排列的。
//prim #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f const int MAXN=55; int dis[MAXN]; int map[MAXN][MAXN]; bool vis[MAXN]; int n,m; void prim() { int sum=0; memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=map[1][i]; vis[1]=true; for(int i=1;i<=n;i++) { int MIN=INF,k=0; for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]<MIN) MIN=dis[j],k=j; vis[k]=true; for(int j=1;j<=n;j++) if(!vis[j]&&map[k][j]<dis[j]) dis[j]=map[k][j]; } for(int i=1;i<=n;i++) sum+=dis[i]; printf("%d\n",sum); } int main() { while(~scanf("%d",&n),n) { memset(map,INF,sizeof(map)); for(int i=1;i<=n;i++) map[i][i]=0; scanf("%d",&m); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); if(map[u][v]>w) map[u][v]=map[v][u]=w;//题目虽然说是单向的，但是在最小生成树中，边都是双向的，所以这道题单边可以直接弄成双边 } prim(); } } //kruskal #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int MAXN=55*55; struct node { int u,v,w; }map[MAXN]; int fa[55]; int n,m,k; bool cmp(node c,node d) { return c.w<d.w; } int find(int p) { return fa[p]==p ? p:fa[p]=find(fa[p]); } void kruskal() { int sum=0; for(int i=0;i<k;i++) { int P=find(map[i].u); int Q=find(map[i].v); if(P!=Q) { sum+=map[i].w; fa[P]=Q; } } printf("%d\n",sum); } int main() { while(~scanf("%d",&n),n) { k=0; scanf("%d",&m); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); map[k].u=u; map[k].v=v; map[k].w=w; k++; } sort(map,map+k,cmp); kruskal(); } }