fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define NMAX 100005
  3. #define LOG 18
  4. using namespace std;
  5. //kiểm tra:
  6. //tên file đọc tệp
  7. //mod,hằng số
  8. //tràn số ,tràn bộ nhớ ,truy cập ko hợp lệ
  9. struct edge{
  10.     int u;
  11.     int v;
  12.     int w;
  13.  
  14. };
  15. int n,m;
  16. int high[NMAX],LCA[NMAX][LOG+1],minimum[NMAX][LOG+1];
  17. vector<pair<int,int>> MST[NMAX];
  18. edge graph[NMAX];
  19. long long result=0;
  20. struct create{
  21.    int leng;
  22.    vector<int> DSU,sizeDSU;
  23.    create(int _n):leng(_n),DSU(leng+1),sizeDSU(leng+1)
  24.    {
  25.        for(int i=1;i<=leng;i++)
  26.        {
  27.            DSU[i]=i;
  28.            sizeDSU[i]=1;
  29.        }
  30.    };
  31.    int find_root(int u)
  32.    {
  33.        return (DSU[u]==u)?u:DSU[u]=find_root(DSU[u]);
  34.    }
  35.    bool join(int u ,int v)
  36.    {
  37.        int root_u=find_root(u);
  38.        int root_v=find_root(v);
  39.        if(root_u==root_v) return false;
  40.        if(sizeDSU[root_u]<sizeDSU[root_v])  swap(root_u,root_v);
  41.        DSU[root_v]=root_u;
  42.        sizeDSU[root_u]+=sizeDSU[root_v];
  43.        return true;
  44.    }
  45. };
  46. void enter()
  47. {
  48.     cin>>n>>m;
  49.     for(int i=1;i<=m;i++)
  50.     {
  51.         cin>>graph[i].u>>graph[i].v>>graph[i].w;
  52.     }
  53.  
  54.  
  55. }
  56. void createMST()
  57. {
  58.     create dsu(n);
  59.     sort(graph+1,graph+m+1,[](edge&a,edge&b){return a.w>b.w;});
  60.     for(int i=1;i<=m;i++)
  61.     {
  62.         int u=graph[i].u;
  63.         int v=graph[i].v;
  64.         int w=graph[i].w;
  65.         if(dsu.join(u,v))
  66.         {
  67.             MST[u].push_back({v,w});
  68.             MST[v].push_back({u,w});
  69.         }
  70.     }
  71. }
  72. void DFS(int node)
  73. {
  74.     for(pair<int,int> u:MST[node])
  75.     {
  76.         if(LCA[node][0]!=u.first)
  77.         {
  78.             LCA[u.first][0]=node;
  79.             high[u.first]=high[node]+1;
  80.             minimum[u.first][0]=u.second;
  81.             DFS(u.first);
  82.         }
  83.     }
  84. }
  85. void createLCA()
  86. {
  87.     for(int j=1;j<=LOG;j++)
  88.     {
  89.         for(int i=1;i<=n;i++)
  90.         {
  91.             LCA[i][j]=LCA[LCA[i][j-1]][j-1];
  92.             minimum[i][j]=min(minimum[i][j-1],minimum[LCA[i][j-1]][j-1]);
  93.         }
  94.     }
  95.     high[0]=-1;
  96. }
  97. int binary_lifting(int u ,int v)
  98. {
  99.     if(high[u]<high[v])
  100.     {
  101.         swap(u,v);
  102.     }
  103.     int ans=INT_MAX;
  104.     for(int i=LOG;i>=0;i--)
  105.     {
  106.         if(high[LCA[u][i]]>=high[v])
  107.         {
  108.             ans=min(ans,minimum[u][i]);
  109.             u=LCA[u][i];
  110.         }
  111.     }
  112.     if(u==v) return ans;
  113.     for(int i=LOG;i>=0;i--)
  114.     {
  115.         if(LCA[u][i]!=LCA[v][i])
  116.         {
  117.             ans=min({ans,minimum[u][i],minimum[v][i]});
  118.             u=LCA[u][i];
  119.             v=LCA[v][i];
  120.         }
  121.     }
  122.     return min({ans,minimum[u][0],minimum[v][0]});
  123. }
  124. void process()
  125. {
  126.     for(int i=1;i<=m;i++)
  127.     {
  128.         result+=max(0,binary_lifting(graph[i].u,graph[i].v)-graph[i].w);
  129.     }
  130.     cout<<result;
  131. }
  132. int main()
  133. {
  134.     ios_base::sync_with_stdio(0);
  135.     cin.tie(nullptr);
  136.     cout.tie(nullptr);
  137.     enter();
  138.     createMST();
  139.     DFS(1);
  140.     createLCA();
  141.     process();
  142.     return 0;
  143. }
  144.  
Success #stdin #stdout 0.01s 5972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A3B4yZ
language:
C++14 (gcc 8.3)
created:
186 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!