文章目錄

• 數(shù)據(jù)結(jié)構(gòu)
• • LCT
  • 線段樹
  • 線段樹分治
  • 樹狀數(shù)組
• 圖論
• • Tarjan
  • 靜態(tài)仙人掌
  • 最小生成樹
  • 最短路-Floyd
  • 最短路-Dijkstra
  • 最短路-Bellman-Ford
  • 最短路-SPFA

數(shù)據(jù)結(jié)構(gòu)

LCT

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 using namespace std; int n, m, g, x, y, v[N], s[N], p[N], fa[N], son[N][2]; bool NR(int x) {return son[fa[x]][0] == x || son[fa[x]][1] == x; } bool IRS(int x) {return son[fa[x]][1] == x; } void push_rev(int x) {swap(son[x][0], son[x][1]);p[x] ^= 1;return; } void push_down(int x) {if (p[x]){if (son[x][0]) push_rev(son[x][0]);if (son[x][1]) push_rev(son[x][1]);p[x] = 0;}return; } void push_up(int x) {s[x] = s[son[x][0]] ^ s[son[x][1]] ^ v[x];return; } void push_hall(int x) {if (NR(x)) push_hall(fa[x]);push_down(x); } void rotate(int x) {int y = fa[x], z = fa[y], k = IRS(x), g = son[x][!k];if (NR(y)) son[z][IRS(y)] = x;if (g) fa[g] = y;son[x][!k] = y;son[y][k] = g;fa[x] = z;fa[y] = x;push_up(y);return; } void Splay(int x) {push_hall(x);while(NR(x)){if (NR(fa[x])){if (IRS(x) == IRS(fa[x])) rotate(fa[x]);else rotate(x);}rotate(x);}push_up(x); } void access(int x) {for (int y = 0; x; y = x, x = fa[x])Splay(x), son[x][1] = y, push_up(x);return; } void make_root(int x) {access(x);Splay(x);push_rev(x);return; } int find_root(int x) {access(x);Splay(x);while(son[x][0]) push_down(x), x = son[x][0];Splay(x);return x; } void Split(int x, int y) {make_root(x);access(y);Splay(y);return; } void link(int x, int y) {make_root(x);if (find_root(y) != x) fa[x] = y; } void cut(int x, int y) {make_root(x);if (find_root(y) == x && fa[y] == x && !son[y][0]){fa[y] = son[x][1] = 0;push_up(x);} } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i)scanf("%d", &v[i]);while(m--){scanf("%d%d%d", &g, &x, &y);if (g == 0){Split(x, y);printf("%d\n", s[y]);}else if (g == 1) link(x, y);else if (g == 2) cut(x, y);else Splay(x), v[x] = y;}return 0; }

線段樹

#include<cstdio> using namespace std; typedef long long ll; ll n,m,u,x,y,z,a[100500]; struct rec {ll l,r,num,lazy; }tree[400500]; ll lazy(ll x){return tree[x].lazy*(tree[x].r-tree[x].l+1);} void up(ll x) {tree[x].num=tree[x*2].num+tree[x*2+1].num+lazy(x*2)+lazy(x*2+1);return; } void make(ll x) {if (tree[x].l==tree[x].r){tree[x].num=a[tree[x].l];return;}ll mid=(tree[x].l+tree[x].r)>>1;tree[x*2].l=tree[x].l,tree[x*2].r=mid;tree[x*2+1].l=mid+1,tree[x*2+1].r=tree[x].r;make(x*2);make(x*2+1);up(x);return; } void pass(ll x) {tree[x*2].lazy+=tree[x].lazy;tree[x*2+1].lazy+=tree[x].lazy;tree[x].num+=lazy(x);tree[x].lazy=0;return; } void change(ll x,ll l,ll r,ll t) {if (tree[x].l==l&&tree[x].r==r){tree[x].lazy+=t;return;}if (tree[x].l>=tree[x].r) return;pass(x);ll mid=(tree[x].l+tree[x].r)>>1;if (r<=mid){change(x*2,l,r,z);up(x);return;}if (l>mid){change(x*2+1,l,r,z);up(x);return;}change(x*2,l,mid,z);change(x*2+1,mid+1,r,z);up(x);return; } ll find(ll x,ll l,ll r) {if (tree[x].l==l&&tree[x].r==r)return tree[x].num+lazy(x);if (tree[x].l>=tree[x].r) return 0;pass(x);ll mid=(tree[x].l+tree[x].r)>>1;if (r<=mid) return find(x*2,l,r);if (l>mid) return find(x*2+1,l,r);return find(x*2,l,mid)+find(x*2+1,mid+1,r); } int main() {scanf("%lld %lld",&n,&m);for (int i=1;i<=n;++i)scanf("%lld",&a[i]);tree[1].l=1;tree[1].r=n;make(1);for (int i=1;i<=m;++i){scanf("%lld",&u);if (u==1){scanf("%lld %lld %lld",&x,&y,&z);change(1,x,y,z);}else{scanf("%lld %lld",&x,&y);printf("%lld\n",find(1,x,y));}} }

線段樹分治

#include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100100 #define mp make_pair #define fs first #define sn second using namespace std; int n,m,k,x,y,xx,yy,w,top,b[N],h[N<<1],fa[N<<1]; vector<pair<int,int> >d[N<<2]; struct de {int x,y,g; }del[N<<1]; int find(int x) {return x==fa[x]?x:find(fa[x]); } void merge(int x,int y) {int X=find(x),Y=find(y);if(h[X]>h[Y])swap(X,Y);del[++top]=(de){X,Y,h[X]==h[Y]};fa[X]=Y;h[Y]=max(h[X]+1,h[Y]);return; } struct Tree {#define ls x*2#define rs x*2+1void add(int x,int L,int R,int l,int r,int u,int v){if(L==l&&R==r){d[x].push_back(mp(u,v));return;}int mid=L+R>>1;if (r<=mid)add(ls,L,mid,l,r,u,v);else if(l>mid)add(rs,mid+1,R,l,r,u,v);else add(ls,L,mid,l,mid,u,v),add(rs,mid+1,R,mid+1,r,u,v);return;}void get(int x,int l,int r){int p=0,lst=top;for(int i=0;i<d[x].size();++i){int X=find(d[x][i].fs),Y=find(d[x][i].sn+n);merge(d[x][i].fs,d[x][i].sn+n);merge(d[x][i].fs+n,d[x][i].sn);if(find(d[x][i].fs)==find(d[x][i].fs+n)){p=1;break;}}if(p)b[l]++,b[r+1]--;else if(l<r){int mid=l+r>>1;get(ls,l,mid);get(rs,mid+1,r);}while(top>lst){fa[del[top].x]=del[top].x;h[del[top].y]=del[top].y-del[top].g;top--;}return;} }T; int main() {scanf("%d%d%d",&n,&m,&k);k++;for(int i=1;i<=m;++i){scanf("%d%d%d%d",&x,&y,&xx,&yy);xx++;if(xx>yy)continue;T.add(1,1,k,xx,yy,x,y);}for(int i=1;i<=n*2;++i)fa[i]=i,h[i]=1;T.get(1,1,k);int sum=0;for(int i=1;i<k;++i){sum+=b[i];if(sum)puts("No");else puts("Yes");}return 0; }

樹狀數(shù)組

#include<cstdio> using namespace std; int n,m,u,x,y,c[500500]; void change(int x,int sum) {for (;x<=n;x+=x&-x)c[x]+=sum; } int find(int x) {int num=0;for (;x;x-=x&-x)num+=c[x];return num; } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;++i){scanf("%d",&x);change(i,x);}for (int i=1;i<=m;++i){scanf("%d%d%d",&u,&x,&y);if (u&1) change(x,y);else printf("%d\n",find(y)-find(x-1));} }

圖論

Tarjan

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 using namespace std; int n, m, x, y, g, w, top, num, tot, ans, d[N], s[N], p[N], deg[N], dfn[N], low[N], head[N]; struct rec {int to, next; }a[N*5]; void add(int x, int y) {a[++tot].to = y;a[tot].next = head[x];head[x] = tot; } void Tarjan(int x) {dfn[x] = low[x] = ++num;d[++top] = x;for (int i = head[x]; i; i = a[i].next){if (!dfn[a[i].to]){Tarjan(a[i].to);low[x] = min(low[x], low[a[i].to]);}elseif (!p[a[i].to])low[x] = min(low[x], dfn[a[i].to]); }if (low[x] == dfn[x]){p[x] = ++w;s[w]++;while(d[top] != x){s[w]++;p[d[top]] = w;top--;}top--;} } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; ++i){scanf("%d%d", &x, &y);add(x, y);}for (int i = 1; i <= n; ++i)if (!dfn[i])Tarjan(i);for (int i = 1; i <= n; ++i)for (int j = head[i]; j; j = a[j].next)if (p[i] != p[a[j].to])deg[p[i]]++;for (int i = 1; i <= w; ++i)if (!deg[i])ans = s[i], g++;if (g == 1) printf("%d", ans);else putchar(48);return 0; }

靜態(tài)仙人掌

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n, m, w, x, y, z, q, X, Y, ex, ans, tot, tott, b[100010], fa[200010], dep[200010], dis[200010], sum[200010], dfn[200010], low[200010], h[200010], head[200010], f[200010][20]; struct rec {ll to, l, next; }e[2000010], a[2000010]; void add(ll x, ll y, ll z) {a[++tot].to = y;a[tot].l = z;a[tot].next = head[x];head[x] = tot;a[++tot].to = x;a[tot].l = z;a[tot].next = head[y];head[y] = tot; } void addd(ll x, ll y, ll z) {e[++tott].to = y;e[tott].l = z;e[tott].next = h[x];h[x] = tott;e[++tott].to = x;e[tott].l = z;e[tott].next = h[y];h[y] = tott; } void jh(ll x, ll y, ll z) {++ex;ll pt = y, ss = z;while(pt != fa[x]){sum[pt] = ss;ss += b[pt];pt = fa[pt];}sum[ex] = sum[x];sum[x] = 0;pt = y;ss = 0;while(pt != fa[x]){ss = min(sum[pt], sum[ex] - sum[pt]);add(pt, ex, ss);pt = fa[pt];} } void dfs(ll x) {dfn[x] = low[x] = ++w;for (int i = h[x]; i; i = e[i].next)if (e[i].to != fa[x]) {ll v = e[i].to;if (!dfn[v]){fa[v] = x;b[v] = e[i].l;dfs(v);low[x] = min(low[x], low[v]);}else low[x] = min(low[x], dfn[v]);if (low[v] > dfn[x]) add(x, v, e[i].l);}for (int i = h[x]; i; i = e[i].next)if ( dfn[e[i].to] > dfn[x] && fa[e[i].to] != x)jh(x, e[i].to, e[i].l); } void dfs1(int x) {dep[x] = dep[f[x][0]] + 1;for (int j = 1; j <= 16; ++j)f[x][j] = f[f[x][j - 1]][j - 1];for (int i = head[x]; i; i = a[i].next)if (a[i].to != f[x][0]){f[a[i].to][0] = x;if (dis[a[i].to]) dis[a[i].to] = min(dis[a[i].to], dis[x] + a[i].l);else dis[a[i].to] = dis[x] + a[i].l;dfs1(a[i].to);} } ll lca(ll x, ll y) {if (dep[x] < dep[y]) swap(x, y);for (int i = 16; i >= 0; --i)if (dep[f[x][i]] >= dep[y]) x = f[x][i];for (int i = 16; i >= 0; --i)if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];X = x;Y = y;return x == y?x:f[x][0]; } int main() {scanf("%d%d%d",&n,&m,&q);ex = n;for (int i = 1; i <= m; ++i){scanf("%d%d%d",&x,&y,&z);addd(x, y, z);}dfs(1);f[1][0] = 1;dfs1(1);for (int i = 1; i <= q; ++i){scanf("%d%d",&x,&y);z = lca(x, y);if (z <= n) ans = dis[x] + dis[y] - dis[z] - dis[z];else{ans = dis[x] - dis[X] + dis[y] - dis[Y]; if (sum[X] > sum[Y]) swap(X, Y);ans += min(sum[Y] - sum[X], sum[z] - sum[Y] + sum[X]);}write(ans);}return 0; }

最小生成樹

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,g,w,x1,y1,ans,dad[5005]; struct rec {int x,y,l; }a[12500005]; int find(int dep){return dad[dep]==dep?dep:dad[dep]=find(dad[dep]);} bool cmp(rec xx,rec yy) {return xx.l<yy.l; } int main() {scanf("%d",&n);for (int i=1;i<=n;++i)dad[i]=i;for (int i=1;i<=n;++i)for (int j=1;j<=n;++j){scanf("%d",&g);if (i>=j) continue;a[++w].x=i;a[w].y=j;a[w].l=g;}sort(a+1,a+1+w,cmp);for (int i=1;i<=w;++i)if (find(a[i].x)!=find(a[i].y)){x1=find(a[i].x);y1=find(a[i].y);dad[min(x1,y1)]=max(x1,y1);ans+=a[i].l;}printf("%d",ans); }

最短路-Floyd

#include<cstdio> #include<cmath> #include<iostream> #include<cstring> using namespace std; int n,m,xx,yy; double f[102][102]; struct rec {int x,y; }a[102]; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d %d",&a[i].x,&a[i].y);scanf("%d",&m);memset(f,0x7f,sizeof(f));for (int i=1;i<=m;i++){scanf("%d %d",&xx,&yy);f[xx][yy]=sqrt(double((a[xx].x-a[yy].x)*(a[xx].x-a[yy].x))+double((a[xx].y-a[yy].y)*(a[xx].y-a[yy].y)));//計算f[yy][xx]=f[xx][yy];}for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if ((i!=j)&&(j!=k)&&(k!=i)&&(f[i][k]+f[k][j]<f[i][j]))f[i][j]=f[i][k]+f[k][j];scanf("%d %d",&xx,&yy);printf("%.2lf",f[xx][yy]); }

最短路-Dijkstra

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; int n,m,xx,yy,l; double f[102][102],b[102],t,maxx; bool c[102]; struct rec {int x,y; }a[102]; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d %d",&a[i].x,&a[i].y);scanf("%d",&m);memset(f,0x7f,sizeof(f));t=f[0][0];for (int i=1;i<=m;i++){scanf("%d %d",&xx,&yy);f[xx][yy]=sqrt(double((a[xx].x-a[yy].x)*(a[xx].x-a[yy].x))+double((a[xx].y-a[yy].y)*(a[xx].y-a[yy].y)));f[yy][xx]=f[xx][yy];}scanf("%d %d",&xx,&yy);for (int i=1;i<=n;i++)b[i]=f[xx][i];b[xx]=0;c[xx]=true;for (int i=2;i<n;i++){maxx=t;l=0;for (int i=1;i<=n;i++)if ((!c[i])&&(b[i]<maxx)){maxx=b[i];l=i;}if (!l) break;c[l]=true;for (int i=1;i<=n;i++)if ((!c[i])&&(b[l]+f[l][i]<b[i]))b[i]=b[l]+f[l][i];}printf("%.2lf",b[yy]);return 0; }

最短路-Bellman-Ford

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int n,m,xx,yy; double b[102]; bool pd; struct rec {int x,y; }a[102]; struct ght {int d1,d2;double jl; }f[100002]; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d %d",&a[i].x,&a[i].y);scanf("%d",&m);for (int i=1;i<=m;i++){scanf("%d %d",&xx,&yy);f[i].jl=sqrt(double((a[xx].x-a[yy].x)*(a[xx].x-a[yy].x))+double((a[xx].y-a[yy].y)*(a[xx].y-a[yy].y)));f[i].d1=xx;f[i].d2=yy;}scanf("%d %d",&xx,&yy);memset(b,0x7f,sizeof(b));b[xx]=0;for (int i=1;i<n;i++){pd=false;for (int j=1;j<=m;j++){if (b[f[j].d1]+f[j].jl<b[f[j].d2]) b[f[j].d2]=b[f[j].d1]+f[j].jl,pd=true;if (b[f[j].d2]+f[j].jl<b[f[j].d1]) b[f[j].d1]=b[f[j].d2]+f[j].jl,pd=true;}if (!pd) break;}printf("%.2lf",b[yy]); }

最短路-SPFA

#include<cstdio> #include<iostream> #include<cmath> #include<queue> using namespace std; int n,m,x,y,a[102],b[102],M,s[102],g; double v[102]; bool p[102]; struct rec {int next,to;double l; }f[1002]; int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d %d",&a[i],&b[i]);scanf("%d",&m);for (int i=1;i<=m;i++){scanf("%d %d",&x,&y);f[++M].l=sqrt(double((a[x]-a[y])*(a[x]-a[y]))+double((b[x]-b[y])*(b[x]-b[y])));f[M].to=y;f[M].next=s[x];s[x]=M;f[++M].l=f[M-1].l;f[M].to=x;f[M].next=s[y];s[y]=M;}queue<int> d;//STLscanf("%d %d",&x,&y);memset(v,0x7f,sizeof(v));d.push(x);p[1]=true;v[x]=0;while(!d.empty()){g=d.front();d.pop();for (int i=s[g];i;i=f[i].next)if (v[g]+f[i].l<v[f[i].to]){v[f[i].to]=v[g]+f[i].l;if (!p[f[i].to]){p[f[i].to]=true;d.push(f[i].to);}}p[g]=false;}printf("%.2lf",v[y]); }

總結(jié)

以上是生活随笔為你收集整理的各种模板（数据结构图论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。