Advertisement
konchin_shih

c495

Jan 31st, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include"./template/headers.hpp"
  2.  
  3. //#define MULTI_TASKCASE
  4. using namespace abb;
  5. using namespace output;
  6. using namespace rit;
  7. using namespace wit;
  8.  
  9. inline void init() {
  10.  
  11. }
  12.  
  13. struct node {int b; ll w; node(int x, ll y): b(x), w(y) {}};
  14. bool operator<(node a, node b) {
  15.     return a.w > b.w;
  16. }
  17. bool operator==(node a, node b) {
  18.     return a.b == b.b && a.w == b.w;
  19. }
  20.  
  21. inline void solve() {
  22.     int n, m;
  23.     cin >> n >> m;
  24.     V<V<node>> edge(n), mst(n);
  25.     while (m--) {
  26.         static ll a, b, w;
  27.         cin >> a >> b >> w, a--, b--;
  28.         edge[a].emplace_back(b, w);
  29.         edge[b].emplace_back(a, w);
  30.     }
  31.     V<ll> d(n, 1e15);
  32.     V<int> p(n, -1);
  33.     V<bool> vis(n, false);
  34.     PQ<node> pq;
  35.     pq.emplace(0, p[0] = d[0] = 0);
  36.     for (int k = 0; k < n; k++) {
  37.         static int a; a = ~0u;
  38.         while (pq.size() && vis[a = pq.top().b]) pq.pop();
  39.         if (!~a) break;
  40.         vis[a] = true;
  41.         for (const auto& i : edge[a])
  42.             if (!vis[i.b] && i.w < d[i.b])
  43.                 pq.emplace(i.b, d[i.b] = i.w), p[i.b] = a;
  44.     }
  45.     ll mstp = accumulate(d.begin(), d.end(), 0ll);
  46.     cout << mstp << ' ';
  47.     for (int i = 1; i < n; i++) {
  48.         mst[p[i]].emplace_back(i, d[i]);
  49.         static int a, b; static ll w;
  50.         a = p[i], b = i, w = d[i];
  51.         edge[a].erase(find(edge[a].begin(), edge[a].end(), node(b, w)));
  52.         edge[b].erase(find(edge[b].begin(), edge[b].end(), node(a, w)));
  53.     }
  54.     V<V<node>> v(n, V<node>(__lg(n), {0, 0}));
  55.     V<int> tin(n), tout(n);
  56.     F<void(int, int, int)> build = [&](int cur, int pre, ll wt) {
  57.         static int t = 0;
  58.         tin[cur] = t++;
  59.         for (int i = 0, k = pre; i < __lg(n); i++) {
  60.             v[cur][i].b = k, v[cur][i].w = max(v[cur][i].w, wt);
  61.             wt = v[k][i].w, k = v[k][i].b;
  62.         }
  63.         for (const auto& i : mst[cur])
  64.             if (i.b != pre) build(i.b, cur, i.w);
  65.         tout[cur] = t++;
  66.     };
  67.     auto isanc = [&](int a, int b) {
  68.         return tin[a] <= tin[b] && tout[a] >= tout[b];
  69.     };
  70.     auto query = [&](int a, int b) {
  71.         if (isanc(a, b)) return a;
  72.         if (isanc(b, a)) return b;
  73.         for (int i = __lg(n) - 1; i >= 0; i--)
  74.             if (!isanc(v[a][i].b, b)) a = v[a][i].b;
  75.         return v[a][0].b;
  76.     };
  77.     auto maxp = [&](int a, int b) {
  78.         int anc = query(a, b);
  79.         ll ret = 0;
  80.         for (int i = __lg(n) - 1; i >= 0; i--) {
  81.             if (!isanc(v[a][i].b, anc)) ret = max(ret, v[a][i].w), a = v[a][i].b;
  82.             if (!isanc(v[b][i].b, anc)) ret = max(ret, v[b][i].w), b = v[b][i].b;
  83.         }
  84.         if (a != anc) ret = max(ret, v[a][0].w);
  85.         if (b != anc) ret = max(ret, v[b][0].w);
  86.         return ret;
  87.     };
  88.     build(0, 0, 0);
  89.     ll diff = 1e18;
  90.     for (int a = 0; a < n; a++)
  91.         for (const auto& i : edge[a])
  92.             diff = min(diff, i.w - maxp(a, i.b));
  93.     cout << mstp + diff << endl;
  94. }
  95.  
  96. main() {
  97.     ios::sync_with_stdio(false);
  98.     init();
  99.     int t = 1;
  100. #ifdef MULTI_TASKCASE
  101.     cin >> t; cin.ignore();
  102. #endif
  103.     while (t--) solve();
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement