fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define INF 1000000005
  4. #define MOD 1000000007
  5. #define EPS 1e-10
  6. #define rep(i,n) for(int i=0;i<(int)(n);++i)
  7. #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
  8. #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
  9. #define each(a,b) for(auto& (a): (b))
  10. #define all(v) (v).begin(),(v).end()
  11. #define len(v) (int)(v).size()
  12. #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
  13. #define cmx(x,y) x=max(x,y)
  14. #define cmn(x,y) x=min(x,y)
  15. #define fi first
  16. #define se second
  17. #define pb push_back
  18. #define show(x) cout<<#x<<" = "<<(x)<<endl
  19. #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
  20. #define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
  21. #define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
  22. #define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
  23. #define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
  24. #define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
  25.  
  26. using namespace std;
  27.  
  28. typedef pair<int,int> P;
  29. typedef pair<ll,ll> pll;
  30. typedef vector<int> vi;
  31. typedef vector<vi> vvi;
  32. typedef vector<ll> vl;
  33. typedef vector<vl> vvl;
  34. typedef vector<double> vd;
  35. typedef vector<P> vp;
  36. typedef vector<string> vs;
  37.  
  38. const int MAX_N = 100005;
  39.  
  40. template<typename _Key, typename _Tp> class Fibonacci_Heap
  41. {
  42. public:
  43.     class node
  44.     {
  45.     public:
  46.         pair<_Key, _Tp> _data;
  47.         unsigned short int _child;
  48.         bool _mark;
  49.         node *_par, *_prev, *_next, *_ch_last;
  50.         node(const _Key& key, const _Tp& data) : _data(key, data),
  51.             _child(0), _par(nullptr), _prev(nullptr), _next(nullptr), _ch_last(nullptr){}
  52.         node(const _Key& key, _Tp&& data) : _data(key, move(data)),
  53.             _child(0), _par(nullptr), _prev(nullptr), _next(nullptr), _ch_last(nullptr){}
  54.         inline const _Key& get_key() const noexcept { return _data.first; }
  55.         void insert(node *cur){
  56.             if(_ch_last) insert_impl(cur, _ch_last);
  57.             else _ch_last = cur, _ch_last->_prev = _ch_last->_next = _ch_last;
  58.             ++_child, cur->_par = this;
  59.         }
  60.         void erase(node *cur){
  61.             if(cur == cur->_prev){
  62.                 _ch_last = nullptr;
  63.             }else{
  64.                 erase_impl(cur);
  65.                 if(cur == _ch_last) _ch_last = cur->_prev;
  66.             }
  67.             --_child, cur->_par = nullptr;
  68.         }
  69.     };
  70.  
  71. private:
  72.     static constexpr float FACTOR = 1.0f / log2((1.0f + sqrt(5.0f)) / 2.0f);
  73.     size_t _size;
  74.     node *_minimum;
  75.     vector<node*> rank;
  76.  
  77.     static void insert_impl(node *cur, node *next){
  78.         cur->_prev = next->_prev, cur->_next = next;
  79.         cur->_prev->_next = cur, next->_prev = cur;
  80.     }
  81.     static void erase_impl(node *cur){
  82.         cur->_prev->_next = cur->_next, cur->_next->_prev = cur->_prev;
  83.     }
  84.     static int ceil2(int u){
  85.         return 32 - __builtin_clz(u);
  86.     }
  87.     void root_insert(node *cur){
  88.         if(_minimum){
  89.             insert_impl(cur, _minimum);
  90.             if(cur->get_key() < _minimum->get_key()) _minimum = cur;
  91.         }else{
  92.             _minimum = cur, _minimum->_prev = _minimum->_next = _minimum;
  93.         }
  94.     }
  95.     void root_erase(node *cur){
  96.         if(cur == cur->_prev) _minimum = nullptr;
  97.         else erase_impl(cur);
  98.     }
  99.     void _delete(node *cur){
  100.         root_erase(cur);
  101.         delete cur;
  102.     }
  103.     template<typename Data>
  104.     node *_push(const _Key& key, Data&& data){
  105.         ++_size;
  106.         node* new_node = new node(key, forward<Data>(data));
  107.         root_insert(new_node);
  108.         return new_node;
  109.     }
  110.     void _pop(){
  111.         assert(_size > 0);
  112.         --_size;
  113.         if(_size == 0){
  114.             _delete(_minimum);
  115.             return;
  116.         }
  117.         if(_minimum->_ch_last){
  118.             for(node *cur = _minimum->_ch_last->_next;;){
  119.                 node *next = cur->_next;
  120.                 _minimum->erase(cur), root_insert(cur);
  121.                 if(!_minimum->_ch_last) break;
  122.                 cur = next;
  123.             }
  124.         }
  125.         unsigned int max_rank = ceil(ceil2(_size) * FACTOR);
  126.         node *next_minimum = _minimum->_next;
  127.         if(rank.size() <= max_rank) rank.resize(max_rank + 1);
  128.         for(node*& cur : rank) cur = nullptr;
  129.         for(node *cur = next_minimum; cur != _minimum;){
  130.             if(cur->get_key() < next_minimum->get_key()) next_minimum = cur;
  131.             node *next = cur->_next;
  132.             unsigned int deg = cur->_child;
  133.             while(rank[deg]){
  134.                 if(cur->get_key() < rank[deg]->get_key() || cur == next_minimum){
  135.                     root_erase(rank[deg]), cur->insert(rank[deg]);
  136.                 }else{
  137.                     root_erase(cur), rank[deg]->insert(cur);
  138.                     cur = rank[deg];
  139.                 }
  140.                 rank[deg++] = nullptr;
  141.             }
  142.             rank[deg] = cur;
  143.             cur = next;
  144.         }
  145.         _delete(_minimum);
  146.         _minimum = next_minimum;
  147.     }
  148.     void _update(node *cur, const _Key& key){
  149.         assert(key >= (_Key)0);
  150.         node *change = ((cur->_data.first -= key) < _minimum->get_key()) ? cur : nullptr;
  151.         if(!cur->_par || cur->_par->get_key() <= cur->get_key()){
  152.             if(change) _minimum = change;
  153.             return;
  154.         }
  155.         while(true){
  156.             node *next = cur->_par;
  157.             next->erase(cur), root_insert(cur);
  158.             cur->_mark = false, cur = next;
  159.             if(!cur->_par) break;
  160.             if(!cur->_mark){
  161.                 cur->_mark = true;
  162.                 break;
  163.             }
  164.         }
  165.         if(change) _minimum = change;
  166.     }
  167.     void clear_dfs(node *cur){
  168.         if(cur->_ch_last){
  169.             for(node *_cur = cur->_ch_last->_next;;){
  170.                 node *next = _cur->_next;
  171.                 if(_cur == cur->_ch_last){
  172.                     clear_dfs(_cur);
  173.                     break;
  174.                 }else{
  175.                     clear_dfs(_cur);
  176.                 }
  177.                 _cur = next;
  178.             }
  179.         }
  180.         delete cur;
  181.         return;
  182.     }
  183.     void _clear(){
  184.         if(!_minimum) return;
  185.         for(node *cur = _minimum->_next;;){
  186.             node *next = cur->_next;
  187.             if(cur == _minimum){
  188.                 clear_dfs(cur);
  189.                 break;
  190.             }else{
  191.                 clear_dfs(cur);
  192.             }
  193.             cur = next;
  194.         }
  195.     }
  196.  
  197. public:
  198.     Fibonacci_Heap() noexcept : _size(0u), _minimum(nullptr){}
  199.     Fibonacci_Heap(const Fibonacci_Heap&) = delete;
  200.     Fibonacci_Heap(Fibonacci_Heap&& another)
  201.         : _size(move(another._size)), rank(move(another.rank)){
  202.         _minimum = another._minimum, another._minimum = nullptr;
  203.     }
  204.     Fibonacci_Heap& operator=(const Fibonacci_Heap&) = delete;
  205.     Fibonacci_Heap& operator=(Fibonacci_Heap&& another){
  206.         _size = move(another._size), rank = move(another.rank);
  207.         _clear(), _minimum = another._minimum, another._minimum = nullptr;
  208.     }
  209.     // ~Fibonacci_Heap(){ _clear(); }
  210.     inline bool empty() const noexcept { return (_size == 0); }
  211.     inline size_t size() const noexcept { return _size; }
  212.     inline const pair<_Key, _Tp>& top() const noexcept { return _minimum->_data; }
  213.     node *push(const _Key& key, const _Tp& data){ return _push(key, data); }
  214.     node *push(const _Key& key, _Tp&& data){ return _push(key, move(data)); }
  215.     void pop(){ _pop(); }
  216.     void update(node *cur, const _Key& key){ _update(cur, key); }
  217.     void clear(){ _clear(); _size = 0; rank.~vector<node*>(); }
  218.     friend Fibonacci_Heap *unite(Fibonacci_Heap *fh1, Fibonacci_Heap *fh2){
  219.         if(fh2->_size == 0){
  220.             fh2->~Fibonacci_Heap();
  221.             return fh1;
  222.         }
  223.         if(fh1->_size == 0){
  224.             fh1->~Fibonacci_Heap();
  225.             return fh2;
  226.         }
  227.         fh1->_minimum->_prev->_next = fh2->_minimum->_next;
  228.         fh2->_minimum->_next->_prev = fh1->_minimum->_prev;
  229.         fh2->_minimum->_next = fh1->_minimum;
  230.         fh1->_minimum->_prev = fh2->_minimum;
  231.         fh1->_size += fh2->_size;
  232.         if(fh1->_minimum->get_key() > fh2->_minimum->get_key()) fh1->_minimum = fh2->_minimum;
  233.         fh2->~Fibonacci_Heap();
  234.         return fh1;
  235.     }
  236.  
  237.     // DEBUG 用
  238.     int dfs(node *cur, bool print, int depth) const {
  239.         if(!cur->_ch_last){
  240.             assert(cur->_child == 0);
  241.             return 1;
  242.         }
  243.         int sz = 1;
  244.         for(node *next = cur->_ch_last->_next; ; next = next->_next){
  245.             if(print) cout << depth << ": " << next->_data.first << " " <<
  246.                         next->_data.second << " " << next->_mark << endl;
  247.             sz += dfs(next, print, depth + 1);
  248.             if(next == cur->_ch_last) break;
  249.         }
  250.         return sz;
  251.     }
  252.     void check(bool print = false) const {
  253.         if(!_minimum){
  254.             assert(_size == 0);
  255.             return;
  256.         }
  257.         size_t sz = 0;
  258.         for(node *cur = _minimum->_next; ; cur = cur->_next){
  259.             if(print) cout << "0: " << cur->_data.first << " " <<
  260.                         cur->_data.second << endl;
  261.             sz += dfs(cur, print, 1);
  262.             if(cur == _minimum) break;
  263.         }
  264.         cout << endl;
  265.         assert(sz == _size);
  266.     }
  267. };
  268.  
  269. class SimpleMergeSet
  270. {
  271. public:
  272.     vector<int> next;
  273.     SimpleMergeSet(const int node_size)
  274.         : next((int)node_size){
  275.         iota(next.begin(), next.end(), 0);
  276.     }
  277.     void unite(const int u, const int v){
  278.         swap(next[u], next[v]);
  279.     }
  280. };
  281.  
  282. template<typename T> class UndirectedMinCut
  283. {
  284. private:
  285.     struct edge{
  286.         int to; T cost; int rev;
  287.         edge(int _to, T _cost, int _rev)
  288.         : to(_to), cost(_cost), rev(_rev){}
  289.     };
  290.     const int V;
  291.     SimpleMergeSet ms;
  292.     vector<vector<edge> > G;
  293.  
  294. public:
  295.     vector<int> ans_set;
  296.     UndirectedMinCut(const int node_size) : V(node_size), ms(V), G(V){}
  297.     void add_edge(int u, int v, T cost){
  298. 		G[u].emplace_back(v, cost, (int)G[v].size());
  299.         G[v].emplace_back(u, cost, (int)G[u].size() - 1);
  300.     }
  301.     T solve(){
  302.         T ans = numeric_limits<T>::max();
  303. 		vector<typename Fibonacci_Heap<T, int>::node*> kp(V, nullptr);
  304. 		vector<int> ord(V);
  305. 		bool *visited = new bool[V]();
  306. 		iota(ord.begin(), ord.end(), 0);
  307.         for(int i = V; i > 1; --i){
  308.             Fibonacci_Heap<T, int> fh;
  309. 			vector<int> new_ord(i-1);
  310.             for(int id : ord){
  311. 				kp[id] = fh.push(0, id);
  312. 			}
  313.             for(int j = 0; j < i-1; ++j){
  314.                 int cur = fh.top().second;
  315.                 fh.pop();
  316.                 visited[cur] = true, new_ord[j] = cur;
  317. 				for(edge& e : G[cur]){
  318. 					if(!visited[e.to]) fh.update(kp[e.to], e.cost);
  319. 				}
  320.             }
  321.             int last_ver = fh.top().second, nx_last = new_ord[i-2];
  322. 			for(edge& e : G[last_ver]){
  323.                 if(e.to == nx_last) continue;
  324. 				G[nx_last].emplace_back(e.to, e.cost, e.rev);
  325.                 edge& reve = G[e.to][e.rev];
  326. 				reve.to = nx_last, reve.rev = (int)G[nx_last].size() - 1;
  327. 			}
  328. 			for(int ver : new_ord){
  329.                 visited[ver] = false;
  330.             }
  331.             visited[last_ver] = true;
  332.             if(ans > -fh.top().first){
  333.                 ans = -fh.top().first;
  334.                 ans_set.clear();
  335.                 for(int cur = last_ver;;){
  336.                     ans_set.push_back(cur);
  337.                     if((cur = ms.next[cur]) == last_ver) break;
  338.                 }
  339.             }
  340.             ms.unite(nx_last, last_ver);
  341.             swap(ord, new_ord);
  342.         }
  343.         delete[] visited;
  344.         return ans;
  345.     }
  346. };
  347.  
  348. int main()
  349. {
  350.     cin.tie(0);
  351.     ios::sync_with_stdio(false);
  352. 	int T;
  353. 	cin >> T;
  354. 	rep(t,T){
  355. 		int n,m;
  356. 		cin >> n >> m;
  357. 		UndirectedMinCut<int> umc(n);
  358. 		rep(i,m){
  359. 			int a,b,c;
  360. 			cin >> a >> b >> c;
  361. 			umc.add_edge(a-1,b-1,c);
  362. 		}
  363. 		cout << "Case #" << t+1 << ": " << umc.solve() << "\n";
  364. 	}
  365.     return 0;
  366. }
  367.  
Runtime error #stdin #stdout #stderr 0s 4296KB
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/mCEPVd
language:
C++14 (gcc 8.3)
created:
4 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!