[C++] 最小生成树(prim) →→→→→进入此内容的聊天室

来自 , 2019-07-02, 写在 C++, 查看 106 次.
URL http://www.code666.cn/view/d68a1827
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<math.h>
  4.  
  5. const int maxn = 100 + 5;
  6. const int INF = 1e9;
  7. int x[maxn];
  8. int y[maxn];
  9. int vis[maxn];
  10. double low[maxn];
  11. double G[maxn][maxn];
  12.  
  13. double prim(int n)
  14. {
  15.     double res = 0;
  16.     double min;
  17.     int i,j,pos;
  18.     vis[1] = 1;
  19.     pos = 1;
  20.     for(i = 1; i <= n; i++)
  21.         if(i != pos) low[i]=G[pos][i];
  22.     for(i=1; i<n; i++)
  23.     {
  24.         min=INF;
  25.         for(j=1; j<=n; j++)
  26.         {
  27.             if(vis[j]==0&&min>low[j])
  28.             {
  29.                 min=low[j];
  30.                 pos=j;
  31.             }
  32.         }
  33.         if(min == INF)
  34.             break;
  35.         res += min;
  36.         vis[pos]=1;
  37.         for(j=1; j<=n; j++)
  38.             if(vis[j]==0 && low[j]>G[pos][j])
  39.                 low[j]=G[pos][j];
  40.     }
  41.     if(i != n)
  42.         return -1;
  43.     return res;
  44. }
  45. int main()
  46. {
  47.     int T;
  48.     scanf("%d",&T);
  49.     while(T--)
  50.     {
  51.         memset(G,0,sizeof(G));
  52.         memset(vis,0,sizeof(vis));
  53.         int n,e;
  54.         scanf("%d",&n);
  55.         for(int i = 1; i <= n; i++)
  56.         {
  57.             scanf("%d%d",&x[i],&y[i]);
  58.             for(int j = 1; j < i; j++)
  59.             {
  60.                 double t = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
  61.                 t = sqrt(t);
  62.                 if(t >= 10.0 && t <= 1000.0)
  63.                     G[i][j] = G[j][i] = t;
  64.                 else
  65.                     G[i][j] = G[j][i] = INF;
  66.             }
  67.         }
  68.         double ans = prim(n);
  69.         ans *= 100;
  70.         if(ans > 0)
  71.             printf("%.1lf\n",ans);
  72.         else
  73.             printf("oh!\n");
  74.     }
  75.     return 0;
  76. }
  77.  

回复 "最小生成树(prim)"

这儿你可以回复上面这条便签

captcha