YEZAELP

TOI16: Water Truck

Nov 27th, 2021
650
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. struct Graph{ int v, w, e; };
  5. const int N = 1e5 + 10;
  6. const int M = 1e5 + 10;
  7. const int inf = 1e9;
  8. using pi = pair <int, int>;
  9. vector <Graph> g[N];
  10. bool bridge[M]; /// edge
  11. bool vs[N];
  12. int deg[N];
  13. void Setting_vs();
  14. int n, m;
  15.  
  16. int counter = 0;
  17. int disc[N], low[N];
  18. void CutBridge(int u, int prevedge){ /// prevedge (parallel edges)
  19.     counter ++;
  20.     vs[u] = true;
  21.     low[u] = counter;
  22.     disc[u] = counter;
  23.     for(auto vwe: g[u]){
  24.         if(vwe.e == prevedge) continue;
  25.         if(!vs[vwe.v]){
  26.             CutBridge(vwe.v, vwe.e);
  27.             low[u] = min(low[u], low[vwe.v]);
  28.             if(low[vwe.v] > disc[u]) bridge[vwe.e] = true;
  29.         }
  30.         else{
  31.             low[u] = min(low[u], disc[vwe.v]);
  32.         }
  33.     }
  34. }
  35.  
  36. vector <int> component[N]; // node in component[i]
  37. void DFSComponent(int u, int prevedge, int comp){
  38.     vs[u] = true;
  39.     component[comp].push_back(u);
  40.     for(auto vwe: g[u]){
  41.         if(vs[vwe.v] or vwe.e == prevedge or bridge[vwe.e]) continue;
  42.         DFSComponent(vwe.v, vwe.e, comp);
  43.     }
  44. }
  45.  
  46. int ShortestPath(int st, int ed){
  47.     Setting_vs();
  48.     priority_queue <pi, vector <pi>, greater <pi>> pq;
  49.     int dis[n + 10]; for(int i=0;i<=n;i++) dis[i] = inf;
  50.     dis[st] = 0;
  51.     pq.push({dis[st], st});
  52.     while(!pq.empty()){
  53.         int d = pq.top().first, u = pq.top().second; pq.pop();
  54.         if(vs[u]) continue; vs[u] = true;
  55.         if(u == ed) return d;
  56.         for(auto vwe: g[u]){
  57.             if(bridge[vwe.e]) continue;
  58.             if(!vs[vwe.v] and d + vwe.w < dis[vwe.v]){
  59.                 dis[vwe.v] = d + vwe.w;
  60.                 pq.push({dis[vwe.v], vwe.v});
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. int main(){
  67.  
  68.     scanf("%d %d", &m, &n);
  69.  
  70.     for(int i=1;i<=m;i++){
  71.         int u, v, w;
  72.         scanf("%d %d %d", &u, &v, &w);
  73.         g[u].push_back({v, w, i});
  74.         g[v].push_back({u, w, i});
  75.     }
  76.  
  77.     CutBridge(0, 0);
  78.  
  79.     Setting_vs();
  80.  
  81.     int sumbridge = 0;
  82.     int sumedge = 0;
  83.     int ncomponent = 0;
  84.     for(int u=0;u<=n;u++){
  85.         for(auto vwe: g[u]){
  86.             if(bridge[vwe.e]) sumbridge += vwe.w;
  87.             else{
  88.                 sumedge += vwe.w;
  89.                 deg[u] ++;
  90.             }
  91.         }
  92.         if(!vs[u]){
  93.             ncomponent ++;
  94.             DFSComponent(u, 0, ncomponent);
  95.         }
  96.     }
  97.     sumbridge /= 2;
  98.     sumedge /= 2;
  99.  
  100.     int sumodddeg = 0;
  101.     for(int i=1;i<=ncomponent;i++){
  102.         vector <int> odddeg;
  103.         for(auto node: component[i]){
  104.             if(deg[node] % 2 == 1) odddeg.push_back(node);
  105.         }
  106.         if(odddeg.size() == 2)
  107.             sumodddeg += ShortestPath(odddeg[0], odddeg[1]);
  108.         else if(odddeg.size() == 4){
  109.             int type1 = ShortestPath(odddeg[0], odddeg[3]) + ShortestPath(odddeg[1], odddeg[2]);
  110.             int type2 = ShortestPath(odddeg[0], odddeg[1]) + ShortestPath(odddeg[2], odddeg[3]);
  111.             int type3 = ShortestPath(odddeg[0], odddeg[2]) + ShortestPath(odddeg[1], odddeg[3]);
  112.             sumodddeg += min({type1, type2, type3});
  113.         }
  114.     }
  115.  
  116.     printf("%d", 2 * sumbridge + sumedge + sumodddeg);
  117.  
  118.     return 0;
  119. }
  120.  
  121.  
  122. void Setting_vs(){
  123.     for(int u=0;u<=n;u++) vs[u] = false;
  124. }
RAW Paste Data