#include using namespace std; typedef int64_t i64; typedef uint64_t ui64; class djset{ private: int sz; int *par; public: djset(int n){ sz=n; par=new int[sz]; for(int i=0;i0) cnt++; } return cnt; } void refr(void){ delete[] par; } }; class graph{ private: struct vrtx{ int to; int64_t cost; }; struct adj{ int start; int to; int64_t cost; }; int nd; int edg; std::vector *node; std::vector edge; public: graph(int n,int m){ nd=n; edg=m; node=new std::vector[nd]; } void add_dir(int s,int t,int64_t c){ node[s].push_back({t,c}); edge.push_back({s,t,c}); } void add_undir(int s,int t,int64_t c){ node[s].push_back({t,c}); node[t].push_back({s,c}); edge.push_back({s,t,c}); } void dlt_dir(int s,int t){ for(int i=0;i().swap(node[i]); delete[] node; std::vector().swap(edge); } bool islnk(void); void dfs(int r,int64_t **p,bool **vst); // 木, (*p)[], vst[] を呼び出す前に初期化 bool ispls(void); void bellford(int s,int64_t **d); void dijkstra(int s,int64_t **d); // 負の閉路なし void bfs(int s,int64_t **d); // 辺に重み無し or 木 void waflo(bool isdir,int64_t ***d); int64_t minstw_dir(int r); // class: djset, class: skewheap が必要 int64_t minstw_undir(void); // class: djset が必要 void edmonds(int r,std::vector> &p); // class: djset, class: skewheap が必要 void kruscal(std::vector> &p); // class: djset が必要 void prim(std::vector> &p); void cumulsum(int s,int64_t **d); // 木 void cumulprd(int s,int64_t **d); // 木 }; int64_t graph::minstw_undir(void){ adj *es=new adj[edg]; for(int i=0;i