首页 > 代码库 > 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