# Untitled

Dec 6th, 2021
712
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. #define LL long long
3. #define N ((int)1e4 + 5)
4. #define MOD ((int)1e9 + 7)
5. #define MAX ((int)1e9 + 7)
6. #define MAXL ((ll)1e18 + 7)
7. #define MAXP ((int)1e3 + 7)
8. #define thr 1e-8
9. #define pi acos(-1)  /// pi = acos ( -1 )
10. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
11. #define endl "\n"
12.
13. using namespace std;
14.
15. //vector < pair < int , int > > bridge;
16.
17. vector < pair < int , int > > edg[N];
18.
19. int par[N] , deg[N] , reach[N] , dep[N], cost[N] , dsu[N] , cnt[N] ;
20. bool vis[N];
21. LL parEdge[N];
22.
23. int dfs(int n , int p , int tot)
24. {
25.     reach[n] = dep[n] = dep[p] + 1;
26.     vis[n] = 1;
27.     par[n] = p;
28.     deg[n] = 1;
29.     int nodes = 1;
32.         if(a == p){
33.             p = -1;
34.             continue;
35.         }
36.         else if(vis[a] == 0){
37.             deg[n]++;
38.             int cnt = dfs(a , n , tot);
39.             nodes += cnt;
40.             if(reach[a] > dep[n]){
41.                 /// found bridge
43.             }
44.             else parEdge[a] = 0;
45.             reach[n] = min(reach[n] , reach[a]);
46.         }
47.         else if(dep[a] < dep[n]){
48.             reach[n] = min(reach[n] , dep[a]);
49.         }
50.     }
51.     return nodes;
52. }
53.
54. void Init(int n)
55. {
56.     for(int i = 1 ; i <= n ; i++){
57.         vis[i] = 0;
58.         edg[i].clear();
59.         dsu[i] = i;
60.         cnt[i] = 1;
61.     }
62.
63. }
64.
65. int FindRoot(int n)
66. {
67.     if(n == dsu[n]) return n;
68.     return dsu[n] = FindRoot(dsu[n]);
69. }
70.
71. void Connect(int a , int b)
72. {
73.     int rootA = FindRoot(a) , rootB = FindRoot(b);
74.     if(rootA != rootB){
75.         dsu[rootB] = rootA;
76.         cnt[rootA] += cnt[rootB];
77.     }
78. }
79.
80. bool Assign(int n , LL MaxCost)
81. {
82.     vector < LL > arr(n+1);
83.     vector < int > Deg(n+1);
84.     for(int i = 1 ; i <= n ; i++) arr[i] = cost[i] , Deg[i] = deg[i];
85.     queue < int > leaf;
86.     for(int i = 1 ; i <= n ; i++) if(Deg[i] == 1 && FindRoot(i) != i) leaf.push(i);
87.     while(!leaf.empty()){
88.         int cur = leaf.front();
89.         leaf.pop();
90.         int p = par[cur];
91.         LL w = parEdge[cur];
92.         //cout<<cur<<" "<<p<<" "<<w<<endl;
93.         if(arr[cur] + w <= MaxCost) arr[cur] += w;
94.         else if(p > 0 && arr[p] + w <= MaxCost) arr[p] += w;
95.         else return false;
96.         Deg[p]--;
97.         if(p > 0 && Deg[p] == 1) leaf.push(p);
98.     }
99.     return true;
100. }
101.
102. void Solve(int caseNo)
103. {
104.     int n , m;
105.     cin>>n>>m;
106.     for(int i = 1 ; i <= n ; i++) cin>>cost[i];
107.     Init(n);
108.     while(m--){
109.         int a, b , w;
110.         cin>>a>>b>>w;
111.         edg[a].push_back({b,w});
112.         edg[b].push_back({a,w});
113.         Connect(a,b);
114.     }
115.     for(int i = 1 ; i <= n ; i++){
116.         if(FindRoot(i) == i) dfs(i , 0 , cnt[i]);
117.     }
118.     LL lef = 0 , rig = 1e17;
119.     while(lef < rig){
120.         LL mid = (lef + rig) >> 1;
121.         if(Assign(n , mid)) rig = mid;
122.         else lef = mid+1;
123.     }
124.     cout<<"Case "<<caseNo<<": "<<lef<<endl;
125. }
126.
127. int main(){
128.     /// problem: https://lightoj.com/problem/reduce-cost
129.     fastio;
130.     int t , caseNo = 1;
131.     cin>>t;
132.     while(t--){
133.         Solve(caseNo++);
134.     }
135.     return 0;
136. }
137.
RAW Paste Data