图论
克鲁斯卡尔 Kruskal template<typename T,size_t V,size_t E> struct Kruskal { typedef tuple<T,int,int> Edge; typedef pair<T,int> PTI; Edge edges[E]; int inmst[E]; int n; // number of vertex int m; // number of edge int uf[V]; int find(int x) { return x==uf[x]?x:uf[x]=find(uf[x]); } void init(int n_) { n=n_; m=0; } void addedge(int u,int v,T w) { edges[m++]={w,u,v}; } PTI solve() { int cnt=n; // number of connected component T sum=0; int u,v; T w; for(int i=0;i<n;i++) uf[i]=i; sort(edges,edges+m); for(int i=0;i<m&&cnt>1;i++) { tie(w,u,v)=edges[i]; u=find(u); v=find(v); if(u==v) continue; inmst[i]=1; sum=sum+w; cnt--; uf[u]=v; } return {sum,cnt==1}; // {totval in mst, ismst} }
…
弗洛伊德 Floyd // T must define < and + template<typename T,size_t V,bool Directed=true,T INF=T(0x3f3f3f3f)> struct Floyd { T g[V][V]; int n; void init(int n_) { n=n_; for(int i=0;i<n;i++) for(int j=0;j<n;j++) g[i][j]=INF; } void addedge(int u,int v,T w) // check multi-edges { g[u][v]=w; if(!Directed) g[v][u]=w; } void cmin(T &x,const T &y) { if(y<x) x=y; } void floyd(Upd =upd) { for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) cmin(g[i][j],g[i][k]+g[k][j]); } };
…
迪杰斯特拉 Dijkstra 模板（priority_queue） // T must define < and + // V: max number of vertex [0~V-1] template<typename T,size_t V,bool Directed=true, T INF=T(0x3f3f3f3f),T ZERO=T(0)> struct G { typedef pair<T,int> PTI; vector<PTI> g[V]; T dis[V]; int vis[V]; int n; void init(int n_) { n=n_; for(int i=0;i<n;i++) g[i].clear(); } void addedge(int u,int v,T w) { g[u].emplace_back(w,v); if(!Directed) g[v].emplace_back(w,u); } void dijkstra(int st,int ed=-1) // ed=-1 no destination { for(int i=0;i<n;i++) dis[i]=INF,vis[i]=0; priority_queue<PTI,vector<PTI>,greater<PTI> > qu; dis[st]=ZERO; qu.emplace(ZERO,st); while(!qu.empty()) { PTI p=qu.top(); qu.pop();
…