SHARE
TWEET

Untitled

a guest Sep 19th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define TESTC ""
  6. #define PROBLEM "uva1494"
  7. #define MAXN 1005
  8. #define PB push_back
  9. #define MP make_pair
  10. #define F first
  11. #define S second
  12.  
  13. #define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)
  14.  
  15. struct Edge
  16. {
  17.     int fr,to;
  18.     double len;
  19.     bool operator < (const Edge& rhs) const
  20.     {
  21.         return len < rhs.len;
  22.     }
  23. };
  24.  
  25.  
  26. int X[MAXN], Y[MAXN], P[MAXN];
  27. int kru[MAXN],num[MAXN];
  28. vector<Edge> edges;
  29. vector<pair<int, double>> G[MAXN];
  30. double Max_cost[MAXN][MAXN];
  31.  
  32. double dis(int x1, int y1, int x2, int y2)
  33. {
  34.     return sqrt(((x2-x1) * (x2-x1)) + ((y2-y1) * (y2-y1)));
  35. }
  36.  
  37. void init()
  38. {
  39.     memset(X,0,sizeof(X));
  40.     memset(Y,0,sizeof(Y));
  41.     memset(P,0,sizeof(P));
  42.     memset(Max_cost,0,sizeof(Max_cost));
  43.     edges.clear();
  44.     for(int i = 0; i < MAXN; i++)
  45.         kru[i] = i, num[i] = 1, G[i].clear();
  46. }
  47.  
  48. int dfs(int u, int v, double Max_num, int pre)
  49. {
  50.     Max_cost[u][v] = max(Max_num, Max_cost[u][v]);
  51.     for (auto i : G[v])
  52.     {
  53.         if (i.F == pre)
  54.             continue;
  55.         double tmp = max(Max_num, i.S);
  56.         dfs(u, i.F, tmp, v);
  57.     }
  58. }
  59.  
  60. int main()
  61. {
  62.     #ifdef DBG
  63.     freopen(PROBLEM TESTC ".in", "r", stdin);
  64.     freopen(PROBLEM ".out", "w", stdout);
  65.     #endif
  66.    
  67.     int t,n;
  68.     cin >> t;
  69.    
  70.     while(t--)
  71.     {
  72.         cin >> n;
  73.         init();
  74.         for (int i = 1; i <= n ; ++i)
  75.         {
  76.             int tmp1,tmp2,tmp3;
  77.             cin >> tmp1 >> tmp2 >> tmp3;
  78.             X[i] = tmp1;
  79.             Y[i] = tmp2;
  80.             P[i] = tmp3;
  81.         }
  82.  
  83.         for(int i = 1; i <= n; ++i)
  84.             for (int j = 1; j < i; ++j)
  85.             {
  86.                 double L = ;
  87.                 edges.push_back({i, j, L});
  88.             }
  89.         sort(edges.begin(),edges.end());
  90.  
  91.         // MST
  92.         double Sum = 0;
  93.         for(int i = 0; i < edges.size(); i++)
  94.         {
  95.             int a = edges[i].fr;
  96.             int b = edges[i].to;
  97.             double l = edges[i].len;
  98.             // printf("%d %d %.lf\n",u,v,l);
  99.             while(a != kru[a])
  100.                 a = kru[a];
  101.             while(b != kru[b])
  102.                 b = kru[b];
  103.            
  104.             if(a != b)
  105.             {
  106.                 if (num[b] >= num[a])
  107.                 {
  108.                     num[b] += num[a];
  109.                     kru[a] = b;
  110.                 }
  111.                 else
  112.                 {
  113.                     num[a] += num[b];
  114.                     kru[b] = a;
  115.                 }
  116.                 G[b].PB(MP(a,l));
  117.                 G[a].PB(MP(b,l));
  118.                 Sum += l;
  119.             }
  120.         }
  121.  
  122.         double ans = 0;
  123.         for(int i = 1; i <= n; i++)
  124.             dfs(i,i,0,-1);
  125.  
  126.         // debug_print
  127.         // printf("%.lf\n",Sum);
  128.         // for(int i = 1; i <= n; i++)
  129.         // {
  130.         //  for(int j = 1; j <= n; j++)
  131.         //  {
  132.         //      printf("%.lf ",Max_cost[i][j]);
  133.         //  }
  134.         //  printf("\n");
  135.         // }
  136.  
  137.         for(int i = 1; i <= n; i++)
  138.             for(int j = i+1; j < n; j++)
  139.                 ans = max(1.0*(P[i]+P[j])/(Sum - Max_cost[i][j]), ans);
  140.         printf("%.2lf\n",ans);
  141.  
  142.     }
  143.     return 0;
  144. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top