首页 > 代码库 > hdu1233
hdu1233
1 #include <iostream> 2 #include <memory.h> 3 #include <cstdio> 4 using namespace std; 5 6 const int MAX = 1<<20; 7 const int N = 111; 8 int mp[N][N]; 9 int lowcost[N];10 int vis[N];11 int n, ans;12 13 void prim()14 {15 int i,j,pos,Min;16 for (i = 1;i <= n; ++ i)17 lowcost[i] = mp[1][i];18 vis[1] = 1;19 for (i = 1;i <= n; ++ i) {20 Min = MAX;21 for (j = 1;j <= n; ++ j) {22 if (Min > lowcost[j] && !vis[j])23 {24 pos = j;25 Min = lowcost[j];26 }27 }28 vis[pos] = 1;29 for (j = 1 ;j <= n; ++ j)30 if (!vis[j] && mp[pos][j] < lowcost[j])31 lowcost[j] = mp[pos][j];32 }33 for (j = 1;j <= n;++ j) //因为mp[1][1] = 034 ans += lowcost[j];35 }36 37 void init()38 {39 memset(lowcost,0,sizeof(lowcost));40 memset(vis,0,sizeof(vis));41 for (int i = 0;i <= n; ++ i)42 for (int j = 0;j <= n;++ j) {43 mp[i][j] = MAX;44 if (i == j)45 mp[i][j] = 0;46 }47 }48 49 50 int main()51 {52 while (~scanf("%d",&n),n)53 {54 init();55 int m = n*(n-1)/2;56 for (int i = 0;i < m; ++ i)57 {58 int a,b,c;59 scanf("%d%d%d",&a,&b,&c); 60 if (mp[a][b] > c)61 mp[a][b] = mp[b][a] = c;62 }63 ans = 0;64 prim();65 cout << ans << endl;66 }67 return 0;68 }
裸体 不解释
hdu1233
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。