• API
• FAQ
• Tools
• Archive
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.

Top