①DJ
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define e exit(0) #define re register #define inf 2147483647 const int N = 10005; const int M = 500005; int n,m,s,cnt,head[N],vis[N],dis[N]; struct bian{int to,next,v;}len[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to,int v){ len[++cnt].v = v; len[cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void DJ(){ for(re int i=1;i<=n;++i) vis[i] = 0,dis[i] = inf; dis[s] = 0; priority_queue<pair<int,int> >Q; Q.push(make_pair(0,s)); while(Q.size()){ int now = Q.top().second; Q.pop(); if(vis[now]) continue; vis[now] = 1; for(re int k=head[now];k;k=len[k].next){ int to = len[k].to,v = len[k].v; if(dis[to] > dis[now]+v){ dis[to] = dis[now]+v; Q.push(make_pair(-dis[to],to)); } } } } int main() { freopen("P3371.in","r",stdin); freopen("P3371.out","w",stdout); n = fd(),m = fd(),s = fd(); for(re int i=1;i<=m;++i){ int x = fd(),y = fd(),v = fd(); add(x,y,v); } DJ(); for(re int i=1;i<=n;++i) printf("%d ",dis[i]); return 0; }
②spfa
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define e exit(0) #define re register #define inf 2147483647 const int N = 10005; const int M = 500005; int n,m,s,cnt,head[N],vis[N],dis[N]; struct bian{int to,next,v;}len[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to,int v){ len[++cnt].v = v; len[cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void spfa(){ for(re int i=1;i<=n;++i) vis[i] = 0,dis[i] = inf; queue<int> Q; vis[s] = 1,dis[s] = 0; Q.push(s); while(Q.size()){ int now = Q.front(); Q.pop();vis[now] = 0; for(re int k=head[now];k;k=len[k].next){ int to = len[k].to,v = len[k].v; if(dis[to] > dis[now]+v){ dis[to] = dis[now]+v; if(!vis[to]){ vis[to] = 1; Q.push(to); } } } } } int main() { n = fd(),m = fd(),s = fd(); for(re int i=1;i<=m;++i){ int x = fd(),y = fd(),v = fd(); add(x,y,v); } spfa(); for(re int i=1;i<=n;++i) printf("%d ",dis[i]); return 0; }
③Floyd
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define inf 2147483647 int n,m,s,f[5010][5010]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int main() { n = fd(),m = fd(),s = fd(); for(re int i=0;i<5010;++i) for(re int j=0;j<5010;++j) if(i == j) f[i][j] = 0; else f[i][j] = inf; for(re int i=1;i<=m;++i){ int x = fd(),y = fd(),v = fd(); f[x][y] = min(f[x][y],v); } for(re int k=1;k<=n;++k) for(re int i=1;i<=n;++i) for(re int j=1;j<=n;++j){ if(f[i][k] == inf||f[k][j] == inf) continue; f[i][j] = min(f[i][j],f[i][k]+f[k][j]); } for(re int i=1;i<=n;++i) printf("%d ",f[s][i]); return 0; }
④最小生成树
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int N = 5005; const int M = 200005; int n,m,fa[N]; long long ans; struct bian{int x,y,v;}len[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int find(int x){ if(x == fa[x]) return x; else return fa[x] = find(fa[x]); } bool cmp(bian a,bian b){return a.v < b.v;} int main() { freopen("P3366.in","r",stdin); freopen("P3366.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=n;++i) fa[i] = i; for(re int i=1;i<=m;++i) len[i].x = fd(),len[i].y = fd(),len[i].v = fd(); sort(len+1,len+1+m,cmp); for(re int i=1;i<=m;++i){ int fa1 = find(len[i].x),fa2 = find(len[i].y); if(fa1 != fa2){ ans += len[i].v; fa[fa1] = fa2; } } printf("%lld",ans); return 0; }
⑤树的直径
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int M = 50005; int n,m,cnt,ans,d[M],vis[M],head[M]; struct bian{int to,next,v;}len[M<<1]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to,int v){ len[++cnt].v = v; len[cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void dfs(int x){ vis[x] = 1; for(re int k=head[x];k;k=len[k].next){ int to = len[k].to,v = len[k].v; if(vis[to]) continue; dfs(to); ans = max(ans,d[x]+d[to]+v); d[x] = max(d[x],d[to]+v); } } void work1(){ dfs(1); printf("%d",ans); } int main() { freopen("P5021.in","r",stdin); freopen("P5021.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=n-1;++i){ int x = fd(),y = fd(),v = fd(); add(x,y,v),add(y,x,v); } if(m == 1){work1();return 0;} return 0; }
⑥Lca
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int N = 5e5+5; int n,m,s,cnt,head[N],vis[N],dis[N],h[N],fa[N],bz[N][24]; struct bian{int to,next;}len[N<<1]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to){ len[++cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void dfs(int x){ for(re int k=head[x];k;k=len[k].next){ int to = len[k].to; if(!h[to]){ h[to] = h[x]+1; fa[to] = x; dfs(to); } } } void makebz(){ for(re int i=1;i<=n;++i) bz[i][0] = fa[i]; for(re int j=1;j<=20;++j) for(re int i=1;i<=n;++i) bz[i][j] = bz[bz[i][j-1]][j-1]; } int Lca(int x,int y){ if(h[x] <= h[y]) swap(x,y); for(re int j=19;j>=0;--j) if(h[bz[x][j]] >= h[y]) x = bz[x][j]; if(x == y) return x; for(re int j=19;j>=0;--j) if(bz[x][j] != bz[y][j]) x = bz[x][j],y = bz[y][j]; return fa[x]; } int main() { freopen("P3379.in","r",stdin); freopen("P3379.out","w",stdout); n = fd(),m = fd(),s = fd(); for(re int i=1;i<=n-1;++i){ int x = fd(),y = fd(); add(x,y),add(y,x); } h[s] = s,fa[s] = s; dfs(s);makebz(); while(m--){ int a = fd(),b = fd(); printf("%d ",Lca(a,b)); } return 0; }
⑦树的重心 NO1.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int M = 5e5+5; int n,cnt,ans,pos,head[M],size[M],vis[M]; struct bian{int to,next;}len[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to){ len[++cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void dfs(int x){ size[x] = vis[x] = 1; int max_part = 0; for(re int k=head[x];k;k=len[k].next){ int to = len[k].to; if(vis[to]) continue; dfs(to); size[x] += size[to]; max_part = max(max_part,size[to]); } max_part = max(max_part,n-size[x]); if(max_part < ans){ ans = max_part; pos = x; } } int main() { freopen("kkk.in","r",stdin); freopen("kkk.out","w",stdout); n = fd(); for(re int i=1;i<=n-1;++i){ int x = fd(),y = fd(); add(x,y); } dfs(1); printf("%d",pos); return 0; }
⑧树的重心 NO2.
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int M = 5e5+5; int n,cnt,vis[M],head[M],maxx[M],fa[M],bz[M][24],ans[M],size[M]; struct bian{int to,next;}len[M<<1]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to){ len[++cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void dfs(int x){ size[x] = vis[x] = 1; for(re int k=head[x];k;k=len[k].next){ int to = len[k].to; if(vis[to]) continue; dfs(to); size[x] += size[to]; maxx[x] = max(maxx[x],size[to]); } } void makebz(){ for(re int j=1;j<=20;++j) for(re int i=1;i<=n;++i) bz[i][j] = bz[bz[i][j-1]][j-1]; } void work(int x){ int pos = x; for(re int j=19;j>=0;--j) if(bz[pos][j]&&maxx[x]*2-size[bz[pos][j]]>0) pos = bz[pos][j]; if(pos != x) pos = fa[pos]; while(pos&&size[x]*2-size[pos]>=0){ if(maxx[x]*2-size[pos]<=0) ans[pos] = x; pos = fa[pos]; } for(re int k=head[x];k;k=len[k].next){ int to = len[k].to; work(to); } } int main() { freopen("kkk.in","r",stdin); freopen("kkk.out","w",stdout); n = fd(); for(re int i=2;i<=n;++i){ fa[i] = fd(); bz[i][0] = fa[i]; add(fa[i],i); } dfs(1);makebz();work(1); return 0; }
⑨二分图最大匹配
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define re register const int M = 2001; int n,m,e,ans,Max,vis[M],match[M],check[M][M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } bool Dfs(int x){ for(re int j=n+1;j<=m+n;++j){ if(!check[x][j]||vis[j]) continue; vis[j] = 1; if(!match[j]||Dfs(match[j])){ match[j] = x; match[x] = j; return true; } } return false; } int main() { freopen("P3386.in","r",stdin); freopen("P3386.out","w",stdout); n = fd(),m = fd(),e = fd(); for(re int i=1;i<=e;++i){ int x = fd(),y = fd(); if(x > n||y > m) continue; y += n; check[x][y] = 1; } memset(match,0,sizeof(match)); for(re int i=1;i<=n;++i){ memset(vis,0,sizeof(vis)); if(match[i]) continue; if(Dfs(i)) ++ans; } printf("%d",ans); return 0; }
二分图最佳匹配(最小费用最大流)
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define e exit(0) #define re register #define inf 2147483647 #define LL int const LL N = 1001; const LL M = 30005; LL n,m,cnt=1,s,t,sum,ans,head[N],dis[N],vis[N],pre[N]; struct bian{LL from,to,v,flow,next;}len[M<<1]; inline LL fd(){ LL s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(LL from,LL to,LL flow,LL v){ len[++cnt].v = v; len[cnt].to = to; len[cnt].flow = flow; len[cnt].from = from; len[cnt].next = head[from]; head[from] = cnt; } bool spfa(){ for(re LL i=0;i<=n;++i) pre[i] = -1,dis[i] = inf,vis[i] = 0; vis[1] = 1,dis[1] = 0; queue<LL> Q; Q.push(1); while(Q.size()){ LL now = Q.front(); Q.pop(); vis[now] = 0; for(re LL k=head[now];k;k=len[k].next){ if(len[k].flow <= 0) continue; LL to = len[k].to,v = len[k].v; if(dis[to] > dis[now]+v){ dis[to] = dis[now]+v; pre[to] = k; if(!vis[to]){ vis[to] = 1; Q.push(to); } } } } if(dis[n] == inf) return false; return true; } void costflow(){ while(spfa()){ LL Min = inf; for(re LL k=pre[n];k!=-1;k = pre[len[k].from]) Min = min(Min,len[k].flow); sum += Min; for(re LL k=pre[n];k!=-1;k = pre[len[k].from]){ ans += Min*len[k].v; len[k].flow -= Min; len[k^1].flow += Min; } } printf("%lld %lld",sum,ans); } int main() { freopen("LOJ102.in","r",stdin); freopen("LOJ102.out","w",stdout); n = fd(),m = fd(); for(re LL i=1;i<=m;++i){ LL x = fd(),y = fd(),flow = fd(),v = fd(); add(x,y,flow,v),add(y,x,0,-v); } costflow(); return 0; }
tarjan.缩点
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<cmath> using namespace std; #define re register const int N = 1e4+5; const int M = 1e5+5; int n,m,c,cnt,lx,deep,ans,top,head[N],col[N],H[N],in[N]; int Q[N],dfn[N],low[N],vis[N],val[N],sum[N],f[N]; struct bian{int from,to,next;}len[M]; struct Eg{int to,next,v;}e[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to){ len[++cnt].to = to; len[cnt].from = from; len[cnt].next = head[from]; head[from] = cnt; } void con(int from,int to,int v){ e[++lx].v = v; e[lx].to = to; e[lx].next = H[from]; H[from] = lx; } void tarjan(int x){ low[x] = dfn[x] = ++deep; Q[++top] = x; vis[x] = 1; for(re int k=head[x];k;k=len[k].next){ int to = len[k].to; if(!dfn[to]){ tarjan(to); low[x] = min(low[x],low[to]); } else if(vis[to]) low[x] = min(low[x],dfn[to]);//防止连到兄弟边. } if(low[x] == dfn[x]){ col[x] = ++c; sum[c] += val[x]; vis[x] = 0; while(top&&Q[top] != x){ vis[Q[top]] = 0; sum[c] += val[Q[top]]; col[Q[top--]] = c; } --top; } } int main() { freopen("P3387.in","r",stdin); freopen("P3387.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=n;++i) val[i] = fd(); for(re int i=1;i<=m;++i){ int x = fd(),y = fd(); add(x,y); } for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); for(re int i=1;i<=cnt;++i){ int x = len[i].from,y = len[i].to; if(col[x] == col[y]) continue; int v = sum[col[y]]; con(col[x],col[y],v); ++in[col[y]]; } queue<int> Q; for(re int i=1;i<=c;++i){ if(!in[i]) Q.push(i); f[i] = sum[i]; } while(Q.size()){ int now = Q.front();Q.pop(); for(re int k=H[now];k;k=e[k].next){ int to = e[k].to,v = e[k].v; f[to] = max(f[to],f[now]+v); --in[to]; if(in[to] == 0) Q.push(to); } } for(re int i=1;i<=c;++i) ans = max(ans,f[i]); printf("%d",ans); return 0; }
tarjan.缩点
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int N = 20005; const int M = 100005; int n,m,cnt,deep,ans,head[N],cut[N],dfn[N],low[N]; struct bian{int to,next;}len[M<<1]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to){ len[++cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void tarjan(int x,int rt,int fa){ int lx = 0; dfn[x] = low[x] = ++deep; for(re int k=head[x];k;k=len[k].next){ int to = len[k].to; if(to == fa) continue; if(!dfn[to]){ if(x == rt) ++lx; tarjan(to,rt,x); low[x] = min(low[x],low[to]); if(low[to] >= dfn[x]&&x != rt) cut[x] = 1; } else low[x] = min(low[x],dfn[to]); } if(x == rt&&lx >= 2) cut[x] = 1; } int main() { freopen("P3388.in","r",stdin); freopen("P3388.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=m;++i){ int x = fd(),y = fd(); add(x,y),add(y,x); } for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i,i); for(re int i=1;i<=n;++i) if(cut[i] == 1) ++ans; printf("%d ",ans); for(re int i=1;i<=n;++i) if(cut[i] == 1) printf("%d ",i); return 0; }
tarjan.桥
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int N = 5e5+5; const int M = 5e5+5; int n,m,cnt,tot,deep,head[N],dfn[N],low[N],E[N][2]; struct bian{int to,next;}len[M]; inline int fd(){ int s=1,t=0; char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void add(int from,int to){ len[++cnt].to = to; len[cnt].next = head[from]; head[from] = cnt; } void tarjan(int x,int fa){ low[x] = dfn[x] = ++deep; for(re int k=head[x];k;k=len[k].next){ int to = len[k].to; if(to == fa) continue; if(!dfn[to]){ tarjan(to,x); low[x] = min(low[x],low[to]); if(low[to] > dfn[x]) E[++tot][0] = x,E[tot][1] = to; } else low[x] = min(low[x],dfn[to]); } } int main() { freopen("kkk.in","r",stdin); freopen("kkk.out","w",stdout); n = fd(),m = fd(); for(re int i=1;i<=m;++i){ int x = fd(),y = fd(); add(x,y),add(y,x); } for(re int i=1;i<=n;++i) if(dfn[i]) tarjan(i,i); return 0; }