单源最短路（dij+堆优化）
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; const int N=500007; priority_queue<pair<int,int> > q; struct edge{ int next,to,w; }; edge e[N<<1]; int head[N],cnt; int d[N],vis[N]; void init(){ cnt=0; memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); memset(d,inf,sizeof(d)); } void add(int u, int v, int w){ e[++cnt]={head[u],v,w}; head[u] = cnt; } void dij(int s){ d[s]=0; q.push(make_pair(0,s)); while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; int w=e[i].w; if(d[v]>d[u]+w){ d[v]=d[u]+w; q.push(make_pair(-d[v],v)); } } } } int main(){ //ios::sync_with_stdio(false); init(); int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } dij(s); for(int i=1;i<=n;i++){ if(i==1) printf("%d",d[i]); else printf(" %d",d[i]); } printf(" "); return 0; }
LCA(倍增)(在线算法) nlogn预处理 logn回答
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; const int N=500007; struct edge{ int next,v; }; edge e[N<<1]; int head[N],cnt,f[N][30],d[N]; void add(int u,int v){ e[++cnt]=(edge){head[u],v}; head[u]=cnt; } int T; void dfs(int u,int fa){ d[u]=d[fa]+1; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(v==fa) continue; f[v][0]=u; for(int j=1;j<=T;j++) f[v][j]=f[f[v][j-1]][j-1]; dfs(v,u); } } int lca(int x,int y){ if(d[x]>d[y]) swap(x,y); for(int i=T;i>=0;i--) if(d[f[y][i]]>=d[x]) y=f[y][i]; if(x==y) return x; for(int i=T;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,s; cin>>n>>m>>s; T=log2(n)+1; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; add(u,v); add(v,u); } dfs(s,0); for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; cout<<lca(x,y)<<" "; } return 0; }
LCA(tarjan并查集优化)(离线算法) n+m回答
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; const int N=500007; struct edge{ int next,v; }; edge e[N<<1]; int head[N],cnt,f[N],vis[N]; vector<pair<int,int> > qu[N]; int ans[N]; void add(int u,int v){ e[++cnt]=(edge){head[u],v}; head[u]=cnt; } int find(int x){ if(x!=f[x]) f[x]=find(f[x]); return f[x]; } void join(int x,int y){ int xx=find(x); int yy=find(y); if(xx!=yy){ f[yy]=xx; } } void tarjan(int u){ vis[u]=1; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(vis[v]) continue; tarjan(v); join(u,v); } vis[u]=2; for(int i=0;i<qu[u].size();i++){ if(vis[qu[u][i].first]==2){ int lca=find(qu[u][i].first); ans[qu[u][i].second]=lca; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,s; cin>>n>>m>>s; for(int i=0;i<=n;i++) f[i]=i; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; add(u,v); add(v,u); } for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; qu[x].push_back(make_pair(y,i)); qu[y].push_back(make_pair(x,i)); } tarjan(s); for(int i=1;i<=m;i++){ cout<<ans[i]<<" "; } return 0; }
tarjan算法(无向图割边)
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const int N=1e6+7; const ll mod=1e9+7; struct edge{ int v,next,w; }; edge e[N<<1]; int head[N],cnt = 1,dfn[N],low[N],num = 0,bridge[N]; void init(){ memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(bridge,0,sizeof(bridge)); cnt=1; num=0; } void add(int u,int v,int w){ e[++cnt]=(edge){v,head[u],w}; head[u]=cnt; } void tarjan(int u,int edge){ dfn[u]=low[u]=++num; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; int w=e[i].w; if(!dfn[v]){ tarjan(v,i); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) bridge[i]=bridge[i^1]=1; }else if(i!=(edge^1)) low[u]=min(low[u],low[v]); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; init(); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } for(int i=1;i<=n;i++){ if(dfn[i]) continue; tarjan(i,0); } int ans=inf; for(int i=2;i<cnt;i+=2){ if(bridge[i]) cout<<e[i^1].v<<" "<<e[i].v<<endl; } return 0; }
tarjan算法(无向图割点)
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const int N=1e5+7; const ll mod=1e9+7; struct edge{ int v,next; }; edge e[N<<1]; int head[N],cnt=0,dfn[N],low[N],num=0,root,cut[N]; void add(int u,int v){ e[++cnt]=(edge){v,head[u]}; head[u]=cnt; } void tarjan(int u){ dfn[u]=low[u]=++num; int flag=0; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); if(dfn[u]<=low[v]){ flag++; if(u!=root||flag>1) cut[u]=1; } }else{ low[u]=min(low[u],dfn[v]); } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; add(u,v); add(v,u); } for(int i=1;i<=n;i++){ if(!dfn[i]){ root=i; tarjan(i); } } int c=0; for(int i=1;i<=n;i++) if(cut[i]) c++; cout<<c<<" "; for(int i=1;i<=n;i++) if(cut[i]) cout<<i<<" "; return 0; }
e-DCC（边双联通分量的求法）
把图中的桥删去后剩下的联通分量就是边双连通分量
#include<bits/stdc++.h> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const int N=1e6+7; const ll mod=1e9+7; struct edge{ int v,next,w; }; edge e[N<<1]; int head[N],cnt = 1,dfn[N],low[N],num = 0,bridge[N]; void init(){ memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(bridge,0,sizeof(bridge)); cnt=1; num=0; } void add(int u,int v,int w){ e[++cnt]=(edge){v,head[u],w}; head[u]=cnt; } void tarjan(int u,int edge){ dfn[u]=low[u]=++num; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; int w=e[i].w; if(!dfn[v]){ tarjan(v,i); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) bridge[i]=bridge[i^1]=1; }else if(i!=(edge^1)) low[u]=min(low[u],low[v]); } } int c[N],dcc=0; void dfs(int u){ c[u]=dcc; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(c[v]||bridge[v]) continue; dfs(v); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; init(); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } for(int i=1;i<=n;i++){ if(dfn[i]) continue; tarjan(i,0); } for(int i=1;i<=n;i++){ if(!c[i]){ ++dcc; dfs(i); } } return 0; }
最大流（EK）
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); const int maxn = 1e5+7; const int inf = 0x3f3f3f3f; const double eps = 1e-6; typedef long long ll; const ll mod = 1e7+9; struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {} }; struct EK { int n, m; vector<Edge> edges; vector<int> G[maxn]; int a[maxn], p[maxn]; void init(int n) { for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } int Maxflow(int s, int t) { int flow = 0; while(1){ memset(a, 0, sizeof(a)); queue<int> Q; Q.push(s); a[s] = inf; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (!a[e.to] && e.cap > e.flow) { p[e.to] = G[x][i]; a[e.to] = min(a[x], e.cap - e.flow); Q.push(e.to); } } if (a[t]) break; } if (!a[t]) break; for (int u = t; u != s; u = edges[p[u]].from) { edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } flow += a[t]; } return flow; } };
最大流（dinic）
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); const int maxn = 1e4+7; const int inf = 0x3f3f3f3f; const double eps = 1e-6; typedef long long ll; const ll mod = 1e7+9; struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {} }; struct Dinic { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; int d[maxn], cur[maxn]; bool vis[maxn]; void init(int n) { for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, inf); } return flow; } };