题意：有n个人，每个人都有自己喜欢用的网络适配器，要你求连接所有人的最小费用
构图的时候每条边的权值等于 两个人用的适配器的费用加上两个人之间网线的费用，然后求最小生成树
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 using namespace std; 7 #define inf 9999999 8 #define N 1005 9 int n,g[N][N],vis[N],dis[N]; 10 int cos[N]; 11 12 int prim(int st) 13 { 14 for(int i=1; i<=n; i++) 15 { 16 dis[i] = g[i][st]; 17 vis[i] = 0; 18 } 19 dis[st] = 0 ; vis[st] = 1; 20 int cost = 0; 21 for(int T=1; T<n; T++) 22 { 23 int mindis = inf , idx = -1; 24 for(int i=1; i<=n; i++) 25 { 26 if(!vis[i]&&dis[i] < mindis) 27 { 28 mindis = dis[i]; 29 idx = i; 30 } 31 } 32 cost += mindis; 33 if(idx == -1) return -1; 34 vis[idx] = 1; 35 for(int i=1; i<=n; i++) 36 { 37 if(!vis[i]&& dis[i]>g[i][idx]) 38 { 39 dis[i] = g[i][idx]; 40 } 41 } 42 } 43 return cost; 44 } 45 46 int main() 47 { 48 int T,val; 49 scanf("%d",&T); 50 while(T--) 51 { 52 for(int i=1; i<=n; i++) 53 for(int j=1; j<=n; j++) 54 { 55 if(i==j) g[i][j] =0; 56 else g[i][j]= inf; 57 } 58 59 scanf("%d",&n); 60 for(int i=1; i<=n; i++) 61 scanf("%d",&cos[i]); 62 for(int i=1; i<=n; i++) 63 for(int j=1; j<=n; j++) 64 { 65 scanf("%d",&val); 66 if(i!=j) g[i][j] = val + cos[i] + cos[j]; 67 } 68 printf("%d\n",prim(1)); 69 } 70 return 0; 71 }
View Code
转载于:https://www.cnblogs.com/ar940507/p/3224190.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/110063.html原文链接：https://javaforall.net
