网站后台要求,山东青岛网站制作,临沂集团网站建设,墙绘网站建设推广文章目录前言图论模板最短路-Floyd最短路-SPFA最短路-Dij堆优化最小生成树-Kruskal最小生成树-Prim堆优化最大匹配-匈牙利算法tarjan求割点tarjan缩点LCA-树上倍增LCA-tarjan并查集优化网络流-最大流dinic网络流-最小费用最大流负环虚树2-SATKruskal重构树静态仙人掌前言
因为…
文章目录前言图论模板最短路-Floyd最短路-SPFA最短路-Dij堆优化最小生成树-Kruskal最小生成树-Prim堆优化最大匹配-匈牙利算法tarjan求割点tarjan缩点LCA-树上倍增LCA-tarjan并查集优化网络流-最大流dinic网络流-最小费用最大流负环虚树2-SATKruskal重构树静态仙人掌前言
因为老是懒得打模板的时候老是扣不到自己的标(因为之前的都打得太丑了)所以导致我十分的不爽。便打算开一个模板库。会不断更新的 图论模板
最短路-Floyd for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j)if(dis[i][k]dis[k][j]dis[i][j])dis[i][j]dis[i][k]dis[k][j];最短路-SPFA
struct edge_node{int to,next,w;
}a[M];
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void spfa(int s)
{memset(f,0x3f,sizeof(f));q.push(s);v[s]1;f[s]0;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y]){v[y]1;q.push(y);}}}v[x]false;}
}最短路-Dij堆优化
#includecstdio
#includecstring
#includequeue
using namespace std;
const int N100010,M200010;
struct node{int pos,dis;bool operator(const node x)const{return x.disdis;}
};
struct edge_node{int to,next,w;
}a[M];
priority_queuenode q;
int tot,ls[N],dis[N],n,m,S;
bool v[N];
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;
}
void dij(int s)
{dis[s]0;q.push((node){s,0});while(!q.empty()){node tmpq.top();q.pop();int xtmp.pos;if(v[x]) continue;v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(dis[y]dis[x]a[i].w){dis[y]dis[x]a[i].w;if(!v[y])q.push(node{y,dis[y]});}}}
}
int main()
{scanf(%d%d%d,n,m,S);memset(dis,0x3f,sizeof(dis));for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);}dij(S);for(int i1;in;i)printf(%d ,dis[i]);
}
}最小生成树-Kruskal
#includecstdio
#includealgorithm
using namespace std;
const int N301,M100010;
struct node{int x,y,w;
}a[M];
int n,m,fa[N],ans,k;
bool cmp(node x,node y)
{return x.wy.w;}
int find(int x)
{return fa[x]x?x:find(fa[x]);}
int main()
{scanf(%d%d,n,m);for(int i1;im;i)scanf(%d%d%d,a[i].x,a[i].y,a[i].w);for(int i1;in;i)fa[i]i;sort(a1,a1m,cmp);for(int i1;im;i){int Fafind(a[i].x),Fbfind(a[i].y);if(Fa!Fb){fa[Fb]Fa;ansa[i].w;k;}if(kn-1) break;}printf(%d %d,k,ans);
}最小生成树-Prim堆优化
这个坑先放着以后再填
最大匹配-匈牙利算法
#includecstdio
#includecstring
using namespace std;
const int N1010;
struct line{int to,next;
}a[N*N];
int link[N],n,m,ls[N],tot,s,e;
bool cover[N];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
bool find(int x)
{int p0;for (int ils[x];i;ia[i].next){int ya[i].to;if (!cover[y]){plink[y];link[y]x;cover[y]true;if (!p || find(p)) return true;link[y]p;}}return false;
}
int main()
{scanf(%d%d%d,n,m,e);for (int i1;ie;i){int x,y;scanf(%d%d,x,y);if(xm||ym) continue;addl(x,y);}for (int i1;in;i){memset(cover,false,sizeof(cover));if (find(i)) s;}printf(%d,s);
}tarjan求割点
#includecstdio
#includealgorithm
#define N 20100
#define M 100100
using namespace std;
struct node{int to,next;
}a[M*2];
int n,m,tot,dfn[N],low[N],ls[N],cnt,z,root;
bool mark[N],v[N];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void tarjan(int x)
{dfn[x]low[x]cnt;int flag0;for(int ils[x];i;ia[i].next){int ya[i].to;v[y]0;if(!dfn[y]){tarjan(y);low[x]min(low[x],low[y]);if(dfn[x]low[y]){flag;if((x!root||flag1)!mark[x])mark[x]1,z;}}else low[x]min(low[x],dfn[y]);}
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);if(xy) continue;addl(x,y);addl(y,x);}for(int i1;in;i)if(!dfn[i]) rooti,tarjan(i);printf(%d\n,z);for(int i1;in;i)if(mark[i]) printf(%d ,i);
}
tarjan缩点
#includecstdio
#includestack
#includequeue
#includecstring
#define N 10000
#define M 100000
using namespace std;
stackint Stack;
queueint q;
struct line{int to,from,next;
}a[M];
int n,m,x,y,tot,in[N],ls[N],fl[N],cost[N],f[N],maxs,low[N],dfn[N],top,num,gt[N],an[N];
bool ins[N],v[N];
void addl(int x,int y,int tot)
{a[tot].toy;a[tot].fromx;a[tot].nextls[x];ls[x]tot;
}
void tarjan(int x)
{ins[x]true;dfn[x]low[x]top;Stack.push(x);for (int ils[x];i;ia[i].next)if (!dfn[a[i].to]){tarjan(a[i].to);low[x]min(low[x],low[a[i].to]);}else if (ins[a[i].to])low[x]min(low[x],dfn[a[i].to]);if (low[x]dfn[x]){while (Stack.top()!x){int yStack.top();fl[y]x;an[x]cost[y];//计算强联通权值和Stack.pop();ins[y]0;}fl[x]x;an[x]cost[x];//计算强联通权值和ins[x]0;Stack.pop();}
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i) scanf(%d,cost[i]);for (int i1;im;i){scanf(%d%d,x,y);addl(x,y,i);//加边}for (int i1;in;i)if (!dfn[i])tarjan(i);//求强联通memset(ls,0,sizeof(ls));//去除所有的边的连通保留值的for (int i1;im;i){xa[i].from;ya[i].to;if (fl[x]!fl[y])//不在强联通中{tot;addl(fl[x],fl[y],tot);//连边in[fl[y]];//统计入度}}
}LCA-树上倍增
#includecstdio
#includealgorithm
#includequeue
#includecmath
#define N 600001
using namespace std;
struct line{int to,next,w;
}a[N*5];
int tot,n,m,s,x,y,ls[N],dep[N],f[N][30],dis[N][30],t;
queueint q;
inline int readn()
{int X0,w0; char c0;while(c0||c9) {w|c-;cgetchar();}while(c0c9) X(X3)(X1)(c^48),cgetchar();return w?-X:X;
}
inline void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
inline void bfs(int s)
{q.push(s);dep[s]1;while(!q.empty()){int xq.front();q.pop();for (int ils[x];i;ia[i].next){int ya[i].to;if (dep[y]) continue;q.push(y);f[y][0]x;dep[y]dep[x]1;dis[y][0]a[i].w;}}t(int)(log(n)/log(2))1;for (int j1;jt;j){for (int i1;in;i){f[i][j]f[f[i][j-1]][j-1];dis[i][j]min(dis[i][j-1],dis[f[i][j-1]][j-1]);}}
}
inline int LCA(int x,int y)
{if (dep[x]dep[y]) swap(x,y);for (int it;i0;i--)if (dep[f[y][i]]dep[x]) yf[y][i];if (xy) return x;for (int it;i0;i--)if (f[y][i]!f[x][i]) {xf[x][i];yf[y][i];}return f[x][0];
}
int main()
{nreadn();mreadn();sreadn();for(int i1;in;i){addl(xreadn(),yreadn(),1);addl(y,x,1);}bfs(s);for(int i1;im;i){printf(%d\n,LCA(readn(),readn()));}
}LCA-tarjan并查集优化
#includecstdio
#includeiostream
using namespace std;
struct line{int next,to;
}a[20001];
int father[10001],n,m,q,p,v[10001],ans,tot,ls[10001],t,x,y,in[10001];
bool ok;
void addl(int x,int y)//加边
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
int find(int x)//并查集优化
{return xfather[x]?x:find(father[x]);
}
void tarjan(int x)
{v[x]1;for (int ils[x];i;ia[i].next)//子节点{int ya[i].to;if (v[y]) continue;tarjan(y);//tarjan一遍father[y]x;//记录祖先}if (ok) return;//标记已找到if (v[q]2 xp){printf(%d\n,find(q));//输出oktrue;return;}if (v[p]2 xq)///输出{printf(%d\n,find(p));oktrue;return;}v[x]2;
}
int main()
{scanf(%d,t);for (;t;t--){scanf(%d,n);tot0;ok0;for (int i1;in;i){ls[i]0;father[i]i;v[i]0;in[i]0;}for (int i1;in;i){scanf(%d%d,x,y);in[y];addl(x,y);addl(y,x);}scanf(%d%d,q,p);for (int i1;in;i)//寻找根if (in[i]0) tarjan(i);//printf(%d\n,ans);}
}网络流-最大流dinic
#includecstdio
#includealgorithm
#includecstring
#includequeue
using namespace std;
const int N10010,M100010,inf2147483647/3;
struct node{int to,next,w;
}a[M*2];
int tot1,n,s,t,m,ans;
int dep[N],ls[N];
queueint q;
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;
}
bool bfs()
{memset(dep,0,sizeof(dep));while(!q.empty()) q.pop();q.push(s);dep[s]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(!dep[y]a[i].w){dep[y]dep[x]1;if(yt) return true;q.push(y);}}}return false;
}
int dinic(int x,int flow)
{int rest0,k;if(xt) return flow;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1dep[y]a[i].w){rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(restflow) return flow;}}if(!rest) dep[x]0;return rest;
}
void netflow()
{while(bfs())ansdinic(s,inf);
}
int main()
{scanf(%d%d%d%d,n,m,s,t);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);}netflow();printf(%d,ans);
}网络流-最小费用最大流
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N5010,M50010,inf2147483647/3;
struct node{int to,w,c,next;
}a[M*2];
queueintq;
int f[N],mf[N],ls[N],pre[N];
int n,s,e,tot,m,anscost,ansflow;
bool v[N];
void addl(int x,int y,int w,int c)
{a[tot].ww;a[tot].toy;a[tot].cc;a[tot].nextls[x];ls[x]tot;a[tot].w0;a[tot].tox;a[tot].c-c;a[tot].nextls[y];ls[y]tot;
}
bool spfa()
{memset(f,0x3f,sizeof(f));memset(v,0,sizeof(v));memset(mf,0,sizeof(mf));q.push(s);f[s]0;v[s]1;mf[s]inf;while(!q.empty()){int xq.front();q.pop();v[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].cf[y]a[i].w){f[y]f[x]a[i].c;mf[y]min(mf[x],a[i].w);pre[y]i;if(!v[y]){v[y]true;q.push(y);}}}}return f[e]2147483647/3;
}
int updata()
{int xe;while(x!s){a[pre[x]].w-mf[e];a[pre[x]^1].wmf[e];xa[pre[x]^1].to;}anscostf[e]*mf[e];ansflowmf[e];
}
void netflow()
{while(spfa())updata();
}
int main()
{tot1;scanf(%d%d%d%d,n,m,s,e);for(int i1;im;i){int x,y,w,c;scanf(%d%d%d%d,x,y,w,c);addl(x,y,w,c);}netflow();printf(%d %d,ansflow,anscost);
}负环
#includecstdio
#includequeue
#includecstring
using namespace std;
const int N2100,M3100;
struct node{int to,next,w;
}a[M*2];
queueint q;
int n,m,tot,ls[N],f[N],cnt[N],T;
bool v[N];
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
bool spfa()
{memset(f,0x3f,sizeof(f));memset(cnt,0,sizeof(cnt));q.push(1);cnt[1]1;f[1]0;v[1]1;while(!q.empty()){int xq.front();v[x]0;q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;cnt[y]cnt[x]1;if(cnt[y]na[i].w0)return true;if(!v[y]){v[y]1;q.push(y);}}} }return false;
}
int main()
{scanf(%d,T);while(T--){ memset(ls,0,sizeof(ls));tot0;scanf(%d%d,n,m);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);if(w0) addl(y,x,w);}if(spfa()) printf(YE5);else printf(N0);putchar(\n);}
}虚树
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N110000;
struct node{int to,next;
}a[2*N];
int n,siz[N],dep[N],son[N],top[N],fa[N];
int tot,ls[N],p[N],ans,cnt,s[N],q,dfn[N],num;
void adde(int x,int y)
{if(xy) return;a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs1(int x)
{siz[x]1;dfn[x]num; for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x]) continue;dep[y]dep[x]1;fa[y]x;dfs1(y);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y; }
}
void dfs2(int x,int fa)
{if(son[x]){top[son[x]]top[x];dfs2(son[x],x);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[x]) continue;top[y]y;dfs2(y,x);}
}
int LCA(int x,int y)
{while(top[x]!top[y])if(dep[top[x]]dep[top[y]]) yfa[top[y]];else xfa[top[x]];if(dep[x]dep[y]) return x;return y;
}
void ins(int x)
{if(!cnt){s[cnt]x;return;}int lcaLCA(s[cnt],x);while(cnt1dep[lca]dep[s[cnt-1]]){adde(s[cnt-1],s[cnt]),cnt--;}if(dep[lca]dep[s[cnt]]) adde(lca,s[cnt--]);if((!cnt)||(s[cnt]!lca)) s[cnt]lca;s[cnt]x;
}
void dp(int x)
{if(siz[x]){for(int ils[x];i;ia[i].next){int ya[i].to;dp(y);if(siz[y]){siz[y]0;ans;}}}else{for(int ils[x];i;ia[i].next){int ya[i].to;dp(y);siz[x]siz[y];siz[y]0;}if(siz[x]1){ans;siz[x]0;}}ls[x]0;
}
bool cmp(int x,int y)
{return dfn[x]dfn[y];}
int main()
{scanf(%d,n);for(int i1;in;i){int x,y;scanf(%d%d,x,y);adde(x,y);adde(y,x);}dfs1(1);top[1]1;dfs2(1,1);tot0;memset(siz,0,sizeof(siz));memset(ls,0,sizeof(ls));scanf(%d,q);while(q--){int k;cnt0;ans0;scanf(%d,k);p[0]1;for(int i1;ik;i){scanf(%d,p[i]);siz[p[i]];}for(int i1;ik;i)if(siz[fa[p[i]]]){puts(-1);p[0]0;break;}if(!p[0]){for(int i1;ik;i)siz[p[i]]--;continue;}sort(p1,p1k,cmp);if(p[1]!1) s[cnt]1;for(int i1;ik;i) ins(p[i]);while(cnt1) adde(s[cnt-1],s[cnt]),cnt--;dp(1);siz[1]tot0;printf(%d\n,ans);}
}2-SAT
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N2e610;
struct node{int to,next;
}a[N*2];
int n,m,tot,cnt,num,ls[N];
int dfn[N],low[N],color[N];
bool ins[N];
stackint S;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void tarjan(int x){dfn[x]low[x]cnt;S.push(x);ins[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(!dfn[y])tarjan(y),low[x]min(low[x],low[y]);else if(ins[y]) low[x]min(low[x],dfn[y]);}if(low[x]dfn[x]){num;while(S.top()!x){ins[S.top()]0;color[S.top()]num;S.pop();}color[S.top()]num;ins[S.top()]0;S.pop();}return;
}
int main()
{scanf(%d%d,n,m);for(int k1;km;k){int i,a,j,b;scanf(%d%d%d%d,i,a,j,b);addl(ia*n,j(!b)*n);addl(jb*n,i(!a)*n);}for(int i1;in*2;i)if(!dfn[i])tarjan(i);for(int i1;in;i)if(color[i]color[in]){printf(IMPOSSIBLE);return 0;}printf(POSSIBLE\n);for(int i1;in;i)printf(%d ,color[i]color[in]);
}
Kruskal重构树
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510;
struct node{int x,y,w;
}e[N];
struct edge_node{int to,next;
}a[N];
int n,m,k,tot,cnt,root,ls[N],val[N];
int top[N],dep[N],siz[N],son[N],fa[N];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
bool cmp(node x,node y)
{return x.wy.w;}
int find(int x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
void dfs1(int x)
{for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x]) continue;dep[y]dep[x]1;fa[y]x;dfs1(y);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}
}
void dfs2(int x)
{if(son[x]){top[son[x]]top[x];dfs2(son[x]);}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x]||yson[x]) continue;top[y]y;dfs2(y);}
}
int LCA(int x,int y)
{while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);xfa[top[x]];}if(dep[x]dep[y]) return x;else return y;
}
int main()
{scanf(%d%d%d,n,m,k);for(int i1;im;i)scanf(%d%d%d,e[i].x,e[i].y,e[i].w);for(int i1;inm;i)fa[i]i;sort(e1,e1m,cmp);cntn;for(int i1;im;i){int fxfind(e[i].x),fyfind(e[i].y);if(fx!fy){fa[fy]fa[fx]cnt;addl(cnt,fx);addl(cnt,fy);addl(fx,cnt);addl(fy,cnt);val[cnt]e[i].w;}}rootfind(1);dfs1(root);top[root]root;dfs2(root);for(int i1;ik;i){int x,y;scanf(%d%d,x,y);printf(%d\n,val[LCA(x,y)]);}
}
静态仙人掌
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e410,K18;
struct node{int to,next,w;
}a[N*2],e[N*2];
int n,m,q,tot,num,cnt;
int f[N][K],s[N],val[N],dep[N],dis[N];
int ls[N],rs[N],dfn[N],low[N];
void addl(int x,int y,int w){a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void adde(int x,int y,int w){e[tot].toy;e[tot].nextrs[x];e[tot].ww;rs[x]tot;
}
void circle(int x,int y,int w){num;int nowy,sumw;while(now!f[x][0]){s[now]sum;sumval[now];nowf[now][0];}sums[num]s[x];s[x]0;nowy;int Dis;while(now!f[x][0]){Dismin(s[now],sum-s[now]);adde(num,now,Dis);adde(now,num,Dis);nowf[now][0];}return;
}
void tarjan(int x){dfn[x]low[x]cnt;int flag0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yf[x][0])continue;if(!dfn[y]){f[y][0]x;val[y]a[i].w;tarjan(y);low[x]min(low[x],low[y]);}else low[x]min(low[x],dfn[y]);if(low[y]dfn[x])continue;adde(x,y,a[i].w);adde(y,x,a[i].w);}for(int ils[x];i;ia[i].next){int ya[i].to;if(xf[y][0]||dfn[x]dfn[y])continue;circle(x,y,a[i].w);}return;
}
void dfs(int x,int fa){for(int irs[x];i;ie[i].next){int ye[i].to;if(yfa)continue;dep[y]dep[x]1;dis[y]dis[x]e[i].w;f[y][0]x;dfs(y,x);}return;
}
int Get_dis(int x,int y){int ux,vy;if(dep[x]dep[y])swap(x,y);for(int iK-1;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];int lca;if(x!y){for(int iK-1;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];lcaf[x][0];}else lcax;if(lcan)return dis[u]dis[v]-dis[lca]*2;else {int ansdis[u]-dis[x]dis[v]-dis[y];return ansmin(s[lca]-abs(s[x]-s[y]),abs(s[x]-s[y]));}
}
int main()
{scanf(%d%d%d,n,m,q);numn;for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}tot0;tarjan(1);dep[1]1;dfs(1,0);for(int i1;iK;i)for(int j1;jnum;j)f[j][i]f[f[j][i-1]][i-1]; for(int i1;iq;i){int x,y;scanf(%d%d,x,y);printf(%d\n,Get_dis(x,y));}
}
