_no0B

Untitled

Dec 6th, 2021
672
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;
  30.     for(auto adj:edg[n]){
  31.         int a = adj.first;
  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
  42.                 parEdge[a] = 1LL*cnt*(tot-cnt)*adj.second;
  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.     fastio;
  129.     int t , caseNo = 1;
  130.     cin>>t;
  131.     while(t--){
  132.         Solve(caseNo++);
  133.     }
  134.     return 0;
  135. }
  136.  
RAW Paste Data