2023年7月30日发(作者：)

算法竞赛常⽤模板（图论篇）个⼈整理，⼤多数⾃⼰写的，少数来⾃⽹络，侵删部分代码⽤到了C++11的新特性（如for-each循环，auto，结构体赋值）。⽬前ACM和PAT⽀持C++17，CCF CSP认证（⼤学⽣）⽀持C++11。但是NOIP和蓝桥杯 不⽀持C++11，使⽤模板时请注意。(4.23 Update: 第⼗四届蓝桥杯⽀持C++11了！！)知识点待补充T_T有向⽆环图（DAG）相关拓扑排序定义（百度百科）：在计算机科学领域，有向图的拓扑排序是对其顶点的⼀种线性排序，使得对于从顶点u到顶点v的每个有向边uv，u在排序中都在v之前。在图论中，由⼀个有向⽆环图（DAG）的顶点组成的序列，当且仅当满⾜下列条件时，才能称为该图的⼀个拓扑排序（英语：Topological sorting）：1.序列中包含每个顶点，且每个顶点只出现⼀次；2.若A在序列中排在B的前⾯，则在图中不存在从B到A的路径。实现：BFS复杂度：O(n+e)（本笔记约定：n为图的点数，e为图的边数）模板题：#include using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N];vectortopo; //拓扑序列void toposort(){ queueq; for(int i=1;i<=n;i++) //让所有⼊度为0的点先⼊队 if(ru[i]==0) (i); while(!()) { int now=(); (); _back(now); for(auto nxt:v[now]) { ru[nxt]--; if(ru[nxt]==0) //⼊度减为0，则⼊队 (nxt); } }}int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) //读⼊每个点的后继，以0结尾 { int now; cin>>now; while(now) { ru[now]++; chu[i]++; v[i].push_back(now); cin>>now; } } toposort(); for(auto i:topo) cout<

缩点+DAG DP#include using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N]; //原图int score2[M]={0}; //DAG点权vectordag[N]; //缩点后的DAGint ru[N]={0},chu[N]={0}; //记录DAG中每个点的⼊度、出度namespace Tarjan{ stacks; bool inStack[N]; int dfn[N], low[N], id[N];

//dfn[i]是i的编号，low[i]表⽰i能到达的最⼩编号，id[i]是i属于的连通分量的编号 int timeStamp=0, scc=0; //时间戳，强连通分量编号 void tarjan(int u) { dfn[u] = low[u] = ++timeStamp; (u); inStack[u] = true; for(auto nxt:v[u]) { if(!dfn[nxt]) { tarjan(nxt); low[u] = min(low[u], low[nxt]); } else if(inStack[nxt]) low[u] = min(low[u], dfn[nxt]); } if(dfn[u]==low[u]) { int now; scc++; do { now = (); (); inStack[now] = false; id[now] = scc; } while(now!=u); } }//end tarjan void suodian() { for(int i=1;i<=n;i++) { score2[id[i]] += score[i]; for(auto nxt:v[i]) if(id[i]!=id[nxt]) { dag[id[i]].push_back(id[nxt]); ru[id[nxt]]++; chu[id[i]]++; } } } //缩点之后，id越⼩拓扑序越靠后 void work() { for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); suodian(); } //根据id排了逆拓扑序}namespace DP{ int f[N]={0}; //f[i]代表以i为终点可获得的最⼤值 void work() { for(int i=Tarjan::scc;i>=1;i--) { f[i] += score2[i]; for(auto nxt:dag[i]) { f[nxt] = max(f[nxt],f[i]); } } int ans = 0; for(int i=Tarjan::scc;i>=1;i--) { if(chu[i]==0) ans = max(ans,f[i]); } cout<>n>>m; for(int i=1;i<=n;i++) cin>>score[i]; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; v[x].push_back(y); } Tarjan::work(); DP::work(); return 0;}有向图的最⼤强连通⼦图模板题：题意：求有向图中的⼀个最⼤点集，其中的点互相可以到达。如果有多个，输出字典序最⼩的。解法：tarjan算法，记录每个强连通分量包含的点的个数，输出点的个数最多的集合即可。#include using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N], xt[N];int dfn[N], low[N], id[N], size[N];int timeStamp=0, scc=0;stacks;bool inStack[N];void tarjan(int u){ low[u] = dfn[u] = ++timeStamp; (u); inStack[u] = true; for(auto nxt:v[u]) { { if(!dfn[nxt]) { tarjan(nxt); low[u] = min(low[u], low[nxt]); } else if(inStack[nxt]) low[u] = min(low[u], dfn[nxt]); } if(dfn[u]==low[u]) { int now; scc++; do { now = (); (); id[now] = scc; inStack[now] = false; size[scc]++; } while(now!=u); }}int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,opt; cin>>x>>y>>opt; //opt==1单向，2双向 v[x].push_back(y); if(opt==2) v[y].push_back(x); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); int maxSize = -1, maxId; for(int i=1;i<=n;i++) { if(maxSize < size[id[i]]) { maxSize = size[id[i]]; maxId = id[i]; } } cout<using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N];stacks;void tarjan(int u, int fa) //此节点，祖先节点{ dfn[u] = low[u] = ++timeStamp; (u); inStack[u] = true; for(auto nxt:v[u]) { if(!dfn[nxt]) { tarjan(nxt, fa); low[u] = min(low[u], low[nxt]); if(low[nxt]>=dfn[u] && u!=fa) //下⼀个点能到达⾃⼰前⾯的点，则⾃⼰⾄关重要 isCut[u] = true; if(u==fa) //祖先节点==⾃⼰，则该节点是根节点，其连接的点就是他⼉⼦ child[u]++; } else if(inStack[nxt]) { low[u] = min(low[u], dfn[nxt]); } } if(child[u]>=2 && u==fa) //是根节点，并且有⾄少两个⼉⼦，则⾄关重要 isCut[u] = true;}int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } for(int i=1;i<=n;i++) { if(!dfn[i]) tarjan(i,i); } int ge = 0; for(int i=1;i<=n;i++) if(isCut[i]) ge++; cout<#include #include #include #define ll long longusing namespace std;vectorv[100005];bool color[100005]; //每个点的颜⾊，⽤0或1表⽰bool vis[100005];bool dfs(int s) //该连通块是否可以染⾊{ bool flag = true; for(auto i:v[s]) //枚举每个邻点 { if(!vis[i]) //没有染⾊ { vis[i] = true; color[i] = !color[s]; //下⼀个点的颜⾊要和这个点相反 flag &= dfs(i); //对下⼀个点进⾏DFS } else if(color[i] == color[s]) //下⼀个点已经染⾊了，且和这个点颜⾊不⼀样 return false; } return flag;}int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; for(int i=1;i<=m;i++) //输⼊m条⽆向边 { int x,y; cin>>x>>y; if(x==y) {cout<<"No"; return 0;} //如果有⾃环，⼀定不是⼆分图 v[x].push_back(y); v[y].push_back(x); } memset(vis,0,sizeof(vis)); memset(color,0,sizeof(color)); bool flag = true; for(int i=1;i<=n;i++) { if(!vis[i]) { vis[i] = true; color[i] = 0; flag &= dfs(i); } }// for(int i=1;i<=n;i++)// cout<using namespace std;vectorlike[1005]; //1-500代表左图，501-1000代表右图int cp[1005]; //-1代表没cp，正整数代表cp编号int pairs = 0;bool vis[1005]; //是否考虑过bool findPair(int x) //让x尝试找CP{ for(auto p:like[x]) //枚举x的每个⼼仪对象 { if(vis[p]) continue; if(cp[x]==p) continue; //换cp换到⾃家的了，赶紧溜 vis[p] = true; if(cp[p]==-1) //如果对⽅没cp { cp[x]=p; cp[p]=x; return true; } else //如果对⽅有cp，让他cp尝试换⼀个cp { if(findPair(cp[p])) //他cp成功换了cp，就可以和p组了 { cp[x]=p; cp[p]=x; return true; } } } return false;}int main(){ ios::sync_with_stdio(false); int n1,n2,m; cin>>n1>>n2>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; y+=500; like[x].push_back(y); like[y].push_back(x); } memset(cp,-1,sizeof cp); for(int i=1;i<=n1;i++) { memset(vis,0,sizeof vis); if(cp[i]==-1) findPair(i); } for(int i=1;i<=n1;i++) pairs += (cp[i]!=-1); cout<using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N];int dis[N]; bool vis[N];void spfa(int s){ memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); queueq; (s); vis[s] = true; dis[s] = 0; while(!()) { int now=(); (); vis[now] = false; for(auto nxt:v[now]) { int &to = , &val = ; if(dis[to] > dis[now] + val) { dis[to] = dis[now] + val; if(!vis[to]) { vis[to] = true; (to); } } } }}const int INF = 0x7fffffff;int main(){ ios::sync_with_stdio(false); cin>>n>>m>>s; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; v[x].push_back({y,z}); } spfa(s); for(int i=1;i<=n;i++) { if(dis[i]!=0x3f3f3f3f) cout<using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N];bool vis[N]; //⼀个点是否在队列中int cnt[N]; //cnt[i]表⽰从起点到i有多少条最短路int dis[N]; //从起点到每个点的距离void spfa(int s,int t) //求s到t的最短路条数{ memset(dis,0x3f,sizeof dis); //fill(cnt+1,cnt+n+1,1); //cnt全赋值为1 queueq; (s); dis[s]=0; cnt[s]=1; while(!()) { int now=(); (); vis[now] = false; if(now==t) continue; //不⽤从终点扩展 for(auto nxt:v[now]) { int to=, val=nxt.v; if(dis[to]>dis[now]+val) { dis[to]=dis[now]+val; cnt[to]=cnt[now]; if(!vis[to]) { vis[to]=true; (to); } } else if(dis[to]==dis[now]+val) //最短路计数 { cnt[to] += cnt[now]; if(!vis[to]) { vis[to]=true; (to); } } } cnt[now] = 0; //⼀定记得每次while之后清零 }}int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; v[x].push_back({y,z}); } spfa(1,n); if(dis[n]==0x3f3f3f3f) cout<<"No answer"; else cout<using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<q; (s); dis[s]=0; cnt[s]=1; while(!()) { int now=(); (); vis[now] = false; if(now==t) continue; //不⽤从终点扩展 for(int i=1;i<=n;i++) { if(a[now][i]==0x3f3f3f3f || now==i) continue; int nxt=i, val=a[now][i]; if(dis[nxt]>dis[now]+val) { dis[nxt]=dis[now]+val; cnt[nxt]=cnt[now]; if(!vis[nxt]) { vis[nxt]=true; (nxt); } } else if(dis[nxt]==dis[now]+val) { cnt[nxt]+=cnt[now]; if(!vis[nxt]) { vis[nxt]=true; (nxt); } } } cnt[now] = 0; //⼀定记得每次while之后清零 }}int main(){ ios::sync_with_stdio(false); cin>>n>>m; memset(a,0x3f,sizeof a); for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; a[x][y] = min(a[x][y], z); } spfa(1,n); if(dis[n]==0x3f3f3f3f) cout<<"No answer"; else cout<using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N];int dis[N]; bool vis[N];void dijkstra(int s) //朴素dijkstra{ memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[s] = 0; for(int i=1;i<=n;i++) { int mn=0x3f3f3f3f, mnid=0; for(int j=1;j<=n;j++) //从未扩展过的点中，找⼀个离s最近的 { if(!vis[j] && mn>dis[j]) { mn = dis[j]; mnid = j; } } int &now = mnid; vis[now] = true; for(auto nxt:v[now]) { dis[] = min(dis[], dis[now] + ); } }}const int INF = 0x7fffffff;int main(){ ios::sync_with_stdio(false); cin>>n>>m>>start; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; v[x].push_back({y,z}); } dijkstra(start); for(int i=1;i<=n;i++) { if(dis[i]!=0x3f3f3f3f) cout<using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)< other.v;}vectorv[N];int n,m,start;priority_queuepq;int dis[N], vis[N];void dijkstra(int s) //堆优化的dijkstra{ memset(dis,0x3f,sizeof dis); dis[s]=0; ({s,233}); while(!()) { int now=().to; (); if(vis[now]) continue; vis[now] = true; for(auto nxt:v[now]) { int nx = ; dis[nx] = min(dis[nx], dis[now]+nxt.v); if(!vis[nx]) ({nx,dis[nx]}); } }}int main(){ ios::sync_with_stdio(false); cin>>n>>m>>start; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; v[x].push_back({y,z}); } dijkstra(start); for(int i=1;i<=n;i++) cout<pq; memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[s] = 0; vis[s] = true; ({s,233}); while(!()) { int now = ().to; (); if(now==t) return dis[t]; for(auto nxt:v[now]) { int &to = , &val = ; if(!harry && special[to]) continue; //lone不能进特殊房间 if(dis[to] > dis[now] + val) { dis[to] = dis[now] + val; if(!vis[to]) { ({to, dis[to]}); vis[to] = true; } } } } return dis[t];}Dijkstra最短路计数最近公共祖先（LCA）#include using namespace std;#define ll long long#define debug(x) {cerr<<#x<<" = "<<(x)<v[N]; //⽤⽆向图存储int depth[N]={0}; //深度（设根深度1）int f[N][LOGN+2]={0}; //f[i][j]为点i向上⾛2^j个点到达的点的编号void init(int rt) //以rt为根建树，并初始化f数组{ memset(depth,0x3f,sizeof(depth)); depth[0] = 0; //哨兵节点深度为0 depth[rt] = 1; //根节点深度为1 queueq; (rt); while(!()) { int now = (); (); for(int nxt:v[now]) //枚举该点每⼀个邻点 { if(depth[nxt] > depth[now]+1) //nxt没被更新过 { //debug(now)debug(nxt) depth[nxt] = depth[now]+1; (nxt); f[nxt][0] = now; for(int k=1;k<=LOGN;k++) { f[nxt][k] = f[f[nxt][k-1]][k-1]; f[nxt][k] = f[f[nxt][k-1]][k-1]; //debug(k)debug(f[nxt][k]) } } } }}int lca(int a,int b){ if(depth[a]=0;k--) //Step1:让两个点跳到同⼀层 { //debug(f[a][k]) if(depth[f[a][k]] >= depth[b]) //跳2^k步仍在b下⾯，则a放⼼跳 a = f[a][k]; } if(a==b) return a; //跳完之后重合了，直接就是祖先 for(int k=LOGN;k>=0;k--) //Step2:让两个点同时跳到LCA下⼀层 { if(f[a][k]!=f[b][k]) { a = f[a][k]; b = f[b][k]; } } return f[a][0];}int main(){ ios::sync_with_stdio(false); cin>>n>>m>>root; for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } init(root); while(m--) { int x,y; cin>>x>>y; cout<