fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. // https://e...content-available-to-author-only...a.org/wiki/Edmonds%27_algorithm
  6. // With link-cut trees to improve performance from O(VE) to O(V^2logV)
  7.  
  8. struct LinkCut{/*{{{*/
  9.   LinkCut *p,*l,*r;
  10.   LinkCut(LinkCut* p=0): p(p), l(0), r(0) {}
  11.  
  12.   bool root() {return not p or p->l != this and p->r != this;}
  13.  
  14.   void rot(LinkCut* LinkCut::*a,LinkCut* LinkCut::*b) {
  15.     if (not root()) (p->l==this?p->l:p->r)=(this->*a);
  16.     (this->*a)->p=p, p=(this->*a);
  17.     (this->*a)=(p->*b), (p->*b)=this;
  18.     if (this->*a) (this->*a)->p=this;
  19.   }
  20.  
  21.   void rotate() {
  22.     if (p->l==this) p->rot(&LinkCut::l,&LinkCut::r);
  23.     else            p->rot(&LinkCut::r,&LinkCut::l);
  24.   }
  25.  
  26.   void splay() {
  27.     while (not root()) {
  28.       if (not p->root()) ((p->l==this)==(p->p->l==p)? p:this)->rotate();
  29.       rotate();
  30.     }
  31.   }
  32.  
  33.   void link(LinkCut* x) {
  34.     splay(); x->splay(); p=x; p->l=this; expose();
  35.   }
  36.  
  37.   void cut() {
  38.     splay(); if (r) r->p=p; p=r=0;
  39.   }
  40.  
  41.   void expose() {
  42.     for (LinkCut* i=this,*j=0; i; j=i,i=i->p) {
  43.       i->splay();
  44.       i->l=j;
  45.     }
  46.     splay();
  47.   }
  48.  
  49.   LinkCut* findroot() {
  50.     expose();
  51.     LinkCut* x=this;
  52.     while (x->r) x=x->r;
  53.     x->expose();
  54.     return x;
  55.   }
  56.  
  57. };/*}}}*/
  58.  
  59. struct Graph{
  60.   int const n;
  61.   vector<vector<int32_t>> edge;
  62.  
  63.   Graph(int n): n(n) {edge.assign(n,vector<int32_t>(n,1<<30));}
  64.  
  65.   int64_t minimum_cost_arborescence(){
  66.     vector<priority_queue<pair<int32_t,int>,vector<pair<int32_t,int>>,greater<pair<int32_t,int>>>> pi(n);
  67.     for (int i=n; i-->1;)
  68.       for (int j=n; j-->0;)
  69.         if (i!=j) pi[i].emplace(edge[j][i],j);
  70.  
  71.     vector<LinkCut> lc(n);
  72.     vector<bool> exists(n,true),merging(n,false);
  73.     vector<int> par(n,-1);
  74.  
  75.     auto const get_pi=[&pi,&exists,this](int i){
  76.       while (not exists[pi[i].top().second] or edge[pi[i].top().second][i]!=pi[i].top().first){
  77.         pi[i].pop();
  78.       }
  79.       return pi[i].top().second;
  80.     };
  81.  
  82.     int64_t res=0;
  83.     for (int i=1; i<n; i++) if (exists[i]){
  84.       int const j=get_pi(i);
  85.  
  86.       // If no conflict, make i a child of j.
  87.       if (lc[j].findroot()!=&lc[i]){
  88.         lc[i].link(&lc[j]);
  89.         res+=edge[j][i];
  90.         par[i]=j;
  91.       }else{
  92.         // Conflict! Rest of cycle goes through a common ancestor.
  93.         vector<int> del={i};
  94.         merging[i]=true;
  95.         for (int x=j; x!=i; x=par[x]){
  96.           del.push_back(x);
  97.           merging[x]=true;
  98.         }
  99.  
  100.         vector<int32_t> old_pi(n);
  101.         for (int b: del){
  102.           if (b==i){
  103.             old_pi[b]=edge[j][b];
  104.           }else{
  105.             old_pi[b]=edge[par[b]][b];
  106.             exists[b]=false;
  107.           }
  108.         }
  109.         res+=edge[j][i];
  110.  
  111.         // Detach edges from the solution that went to deleted nodes.
  112.         vector<int> cycle_children;
  113.         for (int a=1; a<i; a++) if (exists[a] and merging[par[a]]) {
  114.           cycle_children.push_back(a);
  115.           res-=edge[par[a]][a];
  116.           lc[a].cut();
  117.         }
  118.  
  119.         // Merge deleted nodes' edges together, adding new edges for vertex i.
  120.         for (int a=0; a<n; a++) if (exists[a] and a!=i){
  121.           edge[a][i]-=old_pi[i];
  122.         }
  123.         for (int b: del) if (b!=i){
  124.           for (int a=0; a<n; a++) if (a!=i and exists[a]){
  125.             edge[a][i]=min(edge[a][i],edge[a][b]-old_pi[b]);
  126.             edge[i][a]=min(edge[i][a],edge[b][a]);
  127.           }
  128.         }
  129.         // Put the merged node back into the priority queues.
  130.         for (int a=0; a<n; a++) if (exists[a] and a!=i){
  131.           pi[a].emplace(edge[i][a],i);
  132.           pi[i].emplace(edge[a][i],a);
  133.         }
  134.         // Reattach deleted solution edges to the merged vertex.
  135.         for (int a: cycle_children){
  136.           res+=edge[i][a];
  137.           lc[a].link(&lc[i]);
  138.           par[a]=i;
  139.         }
  140.         for (int b: del) {
  141.           merging[b]=false;
  142.         }
  143.         --i;
  144.       }
  145.     }
  146.  
  147.     return res;
  148.   }
  149. };
  150.  
  151. int main(){
  152.   ios::sync_with_stdio(false);
  153.   int n; cin>>n;
  154.   Graph g(n+1);
  155.  
  156.   for (int i=1; i<=n; i++){
  157.     int x,t; cin>>x>>t;
  158.     for (int j=0; j<=n; j++){
  159.       cin>>g.edge[j][i];
  160.     }
  161.     if (x!=i){
  162.       g.edge[x][i]=t;
  163.     }
  164.   }
  165.  
  166.   cout<<g.minimum_cost_arborescence()<<endl;
  167. }
  168.  
Runtime error #stdin #stdout #stderr 0s 15248KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/EhActz
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!