前言第一周训练结束了回顾一下这周所学到的算法。1.Kosaraju用于判断强连通分量核心思想是进行两次dfs第一次类似后序遍历按照访问的先后顺序放入栈中先访问到的先入栈第二次对原图全部反向连接的图进行dfs每次取出栈顶元素按照反向图循序走遇到访问过的就回溯直到无路可走把这个过程走过的点记录下来就是一块强连通分量。如g是原图rg是反向连接的图可以看出{1、2、3、4} {5} {6} 是该图的强连通分量。代码#includebits/stdc.h using namespace std; const int MAX2e55; vectorint g[MAX],rg[MAX]; vectorint vis(MAX,0); vectorvectorint ans; stackint op; int n,m; //第一遍dfs确定op顺序 void dfs(int u){ for(int x:g[u]){ if(!vis[x]){ vis[x]1; dfs(x); } } op.push(u); } //第二遍dfs确定强连通分量 void dfs_temp(int x,vectorinttemp){ for(int y:rg[x]){ if(!vis[y]){ vis[y]1; dfs_temp(y,temp); } } temp.push_back(x); } int main(){ cinnm; for(int i1;im;i){ int u,v; cinuv; g[u].push_back(v); rg[v].push_back(u); } for(int i1;in;i){ if(!vis[i]){ vis[i]1; dfs(i); } } vis.assign(n1,0); while(!op.empty()){ vectorint temp; int xop.top(); coutx ; op.pop(); if(vis[x]) continue; vis[x]1; dfs_temp(x,temp); ans.push_back(temp); } coutendl; for(vectorint x:ans){ for(auto y:x) couty ; coutendl; } return 0; }2.Kruskal重构树看到这个名字的第一反应就是kruskal最小生成树二者的实现思路其实很接近都是每次取最小大边权用并查集判断连通性而不同点是Kruskal重构树需要构造新点对于当前不连通的两点新建一个点来作为二者的父节点同时记录下对应的边长由此可见叶子节点都是原图的点而非终端节点则都是新建的点。该算法主要用于判断u-v所有简单路径边权最大值的最小值或者所有简单路径边权最小值的最大值。如上图是选取u-v所有简单路径最小值的最大值因此是优先处理边权较大的边如5-4对应的最大值就是5和4的公共祖先7对应的w4。代码如下#includebits/stdc.h using namespace std; //原图中两点间所有简单路径的最大边权最小值等于最小生成树上两点之间边权最大值等于重构树上两点 LCA 的点权 //原图中两点间所有简单路径的最小边权最大值等于最大生成树上两点之间边权最小值等于重构树上两点 LCA 的点权 const int MAXM5e45; const int MAXN1e45; //链式前向星 struct edge{ int to,w,next; }e[MAXM1]; struct node{ int u,v,w; bool operator(const nodetemp)const{ return temp.ww; } }; int n,m; int cnt; int head[MAXN1]; mappairint,int,int f; priority_queuenode Node; vectorint father(MAXN1,-1); int tot; unordered_mapint,int key;//存新建点的权值 void add(int u,int v){ cnt; e[cnt].tov; e[cnt].nexthead[u]; head[u]cnt; } int find(int x){ if(father[x]0) return father[x]find(father[x]); return x; } //kruskal void kruskal(){ while(!Node.empty()){ auto tempNode.top(); Node.pop(); temp.ufind(temp.u); temp.vfind(temp.v); if(temp.u!temp.v){ //连左右两边 add(temp.u,tot); add(temp.v,tot); add(tot,temp.u); add(tot,temp.v); //每次融合确保新建的点为father father[temp.u]tot; father[temp.v]tot; key[tot]temp.w; tot; } } } //lca int fa[MAXN1][32],dep[MAXN1],vis[MAXN1]; //LCA直接抄板子 void dfs(int root,int fat){ vis[root]1; fa[root][0]fat; dep[root]dep[fat]1; for(int i1;i31;i) fa[root][i]fa[fa[root][i-1]][i-1]; for(int ihead[root];i;ie[i].next){ if(e[i].tofat) continue; dfs(e[i].to,root); } } int lca(int x,int y){ if(dep[x]dep[y]) swap(x,y); int tempdep[y]-dep[x]; for(int i0;temp;i,temp1){ if(temp1) yfa[y][i]; } if(xy) return y; for(int i31;i0y!x;i--){ if(fa[x][i]!fa[y][i]){ xfa[x][i]; yfa[y][i]; } } return fa[y][0]; } void init(){ cinnm; totn1; for(int i1;im;i){ int u,v,w; cinuvw; f[{u,v}]max(f[{u,v}],w); } for(auto temp:f){ Node.push({temp.first.first,temp.first.second,temp.second}); } kruskal(); for(int i1;itot;i){ if(father[i]-1) dfs(i,0); } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); init(); int q; cinq; while(q--){ int a,b; cinab; if(find(a)!find(b)){ cout-1\n; continue; } else{ coutkey[lca(a,b)]\n; } } return 0; }该代码是P1967 [NOIP 2013 提高组] 货车运输的解法说到这题第一想法是先构造一个最大生成树然后找u-v在改最大生成树上的公共祖先com找出u-com和v-com的最小值代码click here3.单向连通分量判断Asia EC Online 2025第一反应就是任意两点单向连通即可可惜不会写只好悻悻补上。。。核心思想用上面提到的kosaraju算法得到若干强连通分量在将每个分量进行缩点这样就能保证构造出有向无环图接着进行拓扑排序对于该拓扑序列判断任意相邻两点是否存在有向连边。问我为什么是对的古人的智慧。。。如:代码如下#includebits/stdc.h using namespace std; const int MAX2e55; vectorint g[MAX],rg[MAX]; vectorint vis(MAX,0); vectorvectorint ans; stackint op; vectorint color(MAX); int scc0; int n,m; //Kosaraju两次dfs void dfs(int u){ for(int x:g[u]){ if(!vis[x]){ vis[x]1; dfs(x); } } op.push(u); } void dfs_temp(int x,vectorinttemp){ color[x]scc; for(int y:rg[x]){ if(!vis[y]){ vis[y]1; dfs_temp(y,temp); } } temp.push_back(x); } int main(){ cinnm; //Kosaraju for(int i1;im;i){ int u,v; cinuv; g[u].push_back(v); rg[v].push_back(u); } for(int i1;in;i){ if(!vis[i]){ vis[i]1; dfs(i); } } vis.assign(n1,0); while(!op.empty()){ vectorint temp; int xop.top(); op.pop(); if(vis[x]) continue; scc; vis[x]1; dfs_temp(x,temp); ans.push_back(temp); } //缩点构成有向无环图 setint f[scc1]; vectorint deg(scc1,0); for(int i1;in;i){ for(int x:g[i]){ int cicolor[i]; int cxcolor[x]; if(ci!cx!f[ci].count(cx)){ f[ci].insert(cx); deg[cx]; } } } //拓扑排序 vectorint id; queueint deal; for(int i1;iscc;i){ if(deg[i]0) deal.push(i); } while(!deal.empty()){ //对于有多条拓扑排序一定不行因为说明有至少两点同时入度为0则这两点不是单向连通的 if (deal.size()1) { coutNo; return 0; } int xdeal.front(); deal.pop(); id.push_back(x); for(int v:f[x]){ deg[v]--; if(deg[v]0) deal.push(v); } } //判断拓扑序列相邻两点是否连通 int szid.size(); for(int i1;isz;i){ if(!f[id[i-1]].count(id[i])){ coutNo; return 0; } } coutYes; return 0; }4.__int128最小值-2127最大值2127-1上限约 1.7x1038支持运算不支持cin和cout读写#define int __int128 inline void read(int n){ int x0,f1; char chgetchar(); while(ch0||ch9){ if(ch-) f-1; chgetchar(); } while(ch0ch9){ x(x1)(x3)(ch^48); chgetchar(); } nx*f; } inline void print(int n){ if(n0){ putchar(-); n*-1; } if(n9) print(n/10); putchar(n % 10 0); }还有一个数位dp还有点没看懂就等下周更新了hhhh