登录
← 返回首页 | 代码片段 › 3 图论 › 图论 / 搜索
JSON MD

3 图论

含 49 个代码片段
dijkstra (信使) n^2 3.3.1 最短路
27 行
CPP JSON
【dijkstra (信使)(n^2)】 Dijkstra 最短路算法模板,适用于非负权图。 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 26 行 CPP
#include<bits/stdc++.h>
using namespace std;
int i,j,ans,a,b,z,n,m,pan[110],w,mi,f[110][110],dis[110];
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            f[i][j]=0xfffffff;
    for(i=1;i<=n;i++)dis[i]=0xfffffff;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&z);
        f[a][b]=f[b][a]=z;
    }
    for(i=1;i<=n;i++)dis[i]=f[1][i];
    dis[1]=0;pan[1]=1;
    for(i=1;i<=n;i++){
        w=0;mi=0xfffffff;
        for(j=1;j<=n;j++)if(!pan[j]&&dis[j]<mi)mi=dis[w=j];
        if(!w)break;pan[w]=1;
        for(j=1;j<=n;j++)dis[j]=min(dis[j],dis[w]+f[w][j]);
    }
    for(i=1;i<=n;i++)ans=max(ans,dis[i]);
    if(ans==0xfffffff)printf("-1");
    else printf("%d",ans);
    return 0;
}
最小环 (Sightseeing Trip) Floyed 3.3.1 最短路
44 行
CPP JSON
【最小环 (Sightseeing Trip)(Floyed)】 最短路算法模板,求解图中两点间的最短路径。 核心函数: void in(Re &x) — 核心算法函数 void get(Re i,Re j) — 获取值 关键配置: N=103,inf=1e8 复杂度:时间复杂度取决于具体算法 说明:freopen("123.txt","r",stdin); 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=1e8;
int n,m,x,y,z,ans,Ans[N],a[N][N],g[N][N],dis[N][N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void get(Re i,Re j){
	Re k=g[i][j];if(!k)return;
	get(i,k),Ans[++Ans[0]]=k,get(k,j);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=n;++j)
			dis[i][j]=a[i][j]=inf;
	for(Re i=1;i<=n;++i)dis[i][i]=a[i][i]=0;
	while(m--)in(x),in(y),in(z),dis[x][y]=dis[y][x]=a[x][y]=a[y][x]=min(a[x][y],z);
	ans=inf;
	for(Re k=1;k<=n;++k){
		for(Re i=1;i<k;++i)
			for(Re j=i+1,tmp;j<k;++j)	
				if((tmp=dis[i][j]+a[j][k]+a[k][i])<ans){
					ans=tmp,Ans[0]=0;
					Ans[++Ans[0]]=i;
					get(i,j);
					Ans[++Ans[0]]=j;
					Ans[++Ans[0]]=k;
				}
		for(Re i=1;i<=n;++i)
			for(Re j=1,tmp;j<=n;++j)
				if((tmp=dis[i][k]+dis[k][j])<dis[i][j])	
					dis[i][j]=tmp,g[i][j]=k;
	}
	if(ans==inf)puts("No solution.");
	else for(Re i=1;i<=Ans[0];++i)printf("%d ",Ans[i]); 
}
最短路 dijkstra 3.3.1 最短路
38 行
CPP JSON
【最短路(dijkstra)】 Dijkstra 最短路算法模板,适用于非负权图。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void dijkstra(Re st) — Dijkstra最短路 核心结构体:QAQ, QWQ 关键配置: N=1e5+5,M=1e5+5,inf=2e9 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 37 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=1e5+5,inf=2e9;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,d;inline bool operator<(QWQ O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void dijkstra(Re st){
	for(Re i=0;i<=n;++i)dis[i]=inf;
	dis[st]=0,Q.push((QWQ){st,0});
	while(!Q.empty()){
		x=Q.top().x,Q.pop();
		if(pan[x])continue;
		pan[x]=1;
		for(Re i=head[x];i;i=a[i].next)
			if(dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w;
				Q.push((QWQ){to,dis[to]});
			}
	}
}
int main(){
	in(n),in(m),in(st);
	while(m--)in(x),in(y),in(z),add(x,y,z);
	dijkstra(st);
	for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}
最短路 SPFA 3.3.1 最短路
36 行
CPP JSON
【最短路(SPFA)】 SPFA 最短路算法模板,队列优化的 Bellman-Ford。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void SPFA(Re st) — SPFA最短路 核心结构体:QAQ 关键配置: N=1e4+5,M=5e5+5,inf=2147483647 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 35 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=5e5+5,inf=2147483647;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
queue<int>Q;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void SPFA(Re st){
	for(Re i=0;i<=n;++i)dis[i]=inf;
	dis[st]=0,pan[st]=1,Q.push(st);
	while(!Q.empty()){
		x=Q.front(),Q.pop();
		pan[x]=0;
		for(Re i=head[x];i;i=a[i].next)
			if(dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w;
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
}
int main(){
	in(n),in(m),in(st);
	while(m--)in(x),in(y),in(z),add(x,y,z);
	SPFA(st);
	for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}
次短路 SPFA 3.3.1 最短路
44 行
CPP JSON
【次短路(SPFA)】 SPFA 最短路算法模板,队列优化的 Bellman-Ford。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void SPFA(Re st) — SPFA最短路 核心结构体:QAQ 关键配置: N=5003,M=1e5+3,inf=1e9 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=1e5+3,inf=1e9;
int n,m,x,y,z,o,pan[N],head[N],dis[N][2];
struct QAQ{int w,to,next;}a[M<<1];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void SPFA(Re st){
    for(Re i=0;i<=n;++i)dis[i][0]=dis[i][1]=inf;
    dis[st][0]=0,pan[st]=1,Q.push(st);
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to,tmp;i;i=a[i].next){
            if(dis[to=a[i].to][0]>(tmp=dis[x][0]+a[i].w)){
                dis[to][1]=dis[to][0];
                dis[to][0]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
            if(dis[to][1]>(tmp=dis[x][0]+a[i].w)&&tmp>dis[to][0]){
                dis[to][1]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
            if(dis[to][1]>(tmp=dis[x][1]+a[i].w)){
                dis[to][1]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
        }
    }
}
int main(){
    in(n),in(m);
    while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
    SPFA(1);
    printf("%d\n",dis[n][1]);
}
严格次小生成树 add 3.3.2 最小生成树
78 行
CPP JSON
【严格次小生成树】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void dfs(Re x,Re fa) — 深度优先搜索遍历 int lca(Re x,Re y) — 查询最近公共祖先 int ask_max(Re x,Re Ant,Re w) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void kruscal(无参数) — 计算函数 核心结构体:QAQ, QWQ, LCA 关键配置: N=5e5+3,M=5e5+3,logN=19,inf=2e9 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 77 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,M=5e5+3,logN=19,inf=2e9;
int T,n,m,o,root,fa[N],head[N],Tree[M],M1[N][23],M2[N][23];LL MinTree;
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,y,w;inline bool operator<(QWQ O)const{return w<O.w;}}A[M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
struct LCA{
	int deep[N],ant[N][23];
	inline void dfs(Re x,Re fa){
		deep[x]=deep[fa]+1,ant[x][0]=fa;
		for(Re i=1;(1<<i)<=deep[x];++i){
			ant[x][i]=ant[ant[x][i-1]][i-1];
			M1[x][i]=max(M1[x][i-1],M1[ant[x][i-1]][i-1]);
			M2[x][i]=max(M2[x][i-1],M2[ant[x][i-1]][i-1]);
			if(M1[x][i-1]!=M1[ant[x][i-1]][i-1])
				M2[x][i]=max(M2[x][i],min(M1[x][i-1],M1[ant[x][i-1]][i-1]));
		}
		for(Re i=head[x],to;i;i=a[i].next)
			if((to=a[i].to)!=fa)M1[to][0]=a[i].w,M2[to][0]=-inf,dfs(to,x);
	}
	inline int lca(Re x,Re y){
		if(deep[x]>deep[y])swap(x,y);
		for(Re i=logN;i>=0;--i)if(deep[x]<=deep[y]-(1<<i))y=ant[y][i];
		if(x==y)return y;
		for(Re i=logN;i>=0;--i)
			if(ant[x][i]^ant[y][i])x=ant[x][i],y=ant[y][i];
		return ant[x][0];
	}
	inline int ask_max(Re x,Re Ant,Re w){
		Re ans=-inf;
		for(Re i=logN;i>=0;--i)
			if(deep[ant[x][i]]>=deep[Ant]){
				if(w!=M1[x][i])ans=max(ans,M1[x][i]);
				else ans=max(ans,M2[x][i]);
				x=ant[x][i];
			}
		return ans;
	}
}T1;
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void kruscal(){
	sort(A+1,A+m+1);
	for(Re i=1;i<=n;++i)fa[i]=i;
	for(Re i=1;i<=m;++i){
		Re x=A[i].x,y=A[i].y,w=A[i].w;
		if(find(x)!=find(y)){
			MinTree+=w,Tree[i]=1;
			add(x,y,w),add(y,x,w);
			fa[find(x)]=find(y);
		}
	}
}
int main(){
	in(n),in(m),root=1;
	for(Re i=1;i<=m;++i)in(A[i].x),in(A[i].y),in(A[i].w);
	kruscal();
	M1[root][0]=0,M2[root][0]=-inf,T1.dfs(root,0);
	LL ans=1e17;
	for(Re i=1;i<=m;++i)
		if(!Tree[i]){
			Re x=A[i].x,y=A[i].y,w=A[i].w;
			Re lca=T1.lca(x,y);
			ans=min(ans,MinTree+w-max(T1.ask_max(x,lca,w),T1.ask_max(y,lca,w)));
		}
	printf("%lld",ans);
}
曼哈顿距离最小生成树 Object Clustering 3.3.2 最小生成树
63 行
CPP JSON
【曼哈顿距离最小生成树(Object Clustering)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 LL Abs(LL a) — 核心算法函数 LL Dis(Re x,Re y) — 核心算法函数 void CL(无参数) — 核心算法函数 void add(Re x,Re v,Re ID) — 加法更新 LL ask(Re x) — 核心算法函数 LL find_(Re x) — 查找(并查集寻根/二分查找) LL find(Re x) — 查找(并查集寻根/二分查找) 核心结构体:QAQ, Point, BIT 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 说明:freopen("123.txt","r",stdin); 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const LL N=1e4+3;
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
LL n,m,x,y,t,K,Ans,b[N];
struct QAQ{LL x,y,v;inline bool operator<(const QAQ &O)const{return v<O.v;}}a[N<<3];
struct Point{LL x,y,id;inline bool operator<(const Point &O)const{return x!=O.x?x<O.x:y<O.y;}}P[N];
inline LL Abs(LL a){return a<0?-a:a;}
inline LL Dis(Re x,Re y){return Abs(P[x].x-P[y].x)+Abs(P[x].y-P[y].y);}
struct BIT{
	LL n,C[N],id[N];
	inline void CL(){memset(C,127,sizeof(C));}
	inline void add(Re x,Re v,Re ID){while(x){if(v<C[x])C[x]=v,id[x]=ID;x-=x&-x;}}
	inline LL ask(Re x){Re Min=1e18,ID=0;while(x<=n){if(C[x]<Min)Min=C[x],ID=id[x];x+=x&-x;}return ID;}
}TR;
inline LL find_(Re x){
	Re l=1,r=t;
	while(l<r){
		Re mid=(l+r+1)>>1;
		if(b[mid]<=x)l=mid;
		else r=mid-1;
	}
	return l;
}
LL fa[N];
inline LL find(Re x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void kruscal(){
	for(Re O=1;O<=4;++O){
		if(!(O&1))for(Re i=1;i<=n;++i)swap(P[i].x,P[i].y);
		else if(O==3)for(Re i=1;i<=n;++i)P[i].x*=-1;
		sort(P+1,P+n+1);
		for(Re i=1;i<=n;++i)b[i]=P[i].y-P[i].x;
		sort(b+1,b+n+1),t=unique(b+1,b+n+1)-b-1;
		TR.n=t,TR.CL();
		for(Re i=n;i>=1;--i){
			Re I=find_(P[i].y-P[i].x),j=TR.ask(I);
			if(j)a[++m]=(QAQ){P[i].id,P[j].id,Dis(i,j)};
			TR.add(I,P[i].x+P[i].y,i);
		}
	}
	sort(a+1,a+m+1);
	for(Re i=1;i<=n;++i)fa[i]=i;
	for(Re i=1,t=0;i<=m&&t<n-1;++i)if((x=find(a[i].x))!=(y=find(a[i].y))){
		fa[x]=y,Ans+=a[i].v;
		if(++t==K)printf("%lld\n",a[i].v);
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(K),K=n-1-K+1;
	for(Re i=1;i<=n;++i)in(P[i].x),in(P[i].y),P[i].id=i;
	kruscal();
}
最小生成树 Kruscal 3.3.2 最小生成树
26 行
CPP JSON
【最小生成树(Kruscal)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) 核心结构体:QAQ 关键配置: N=5003,M=2e5+3 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 25 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3;
int n,m,ans,fa[N];
struct QAQ{int x,y,w;inline bool operator<(const QAQ &O)const{return w<O.w;};}A[M];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	in(n),in(m);
	for(Re i=1;i<=n;++i)fa[i]=i;
	for(Re i=1;i<=m;++i)in(A[i].x),in(A[i].y),in(A[i].w);
	sort(A+1,A+m+1);
	for(Re i=1,t=0;i<=m&&t<n-1;++i){
		Re x=find(A[i].x),y=find(A[i].y);
		if(x!=y)++t,ans+=A[i].w,fa[x]=y;
	}
	printf("%d",ans);
}
最小生成树 LCT 3.3.2 最小生成树
88 行
CPP JSON
【最小生成树(LCT)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void pushup(Re p) — 上推更新节点信息 void updata(Re p) — 核心算法函数 void pushdown(Re p) — 下传懒标记 int nort(Re p) — 核心算法函数 int which(Re p) — 核心算法函数 void connect(Re p,Re fa,Re o) — 核心算法函数 void rotate(Re p) — 旋转操作(平衡树) 核心结构体:Link_Cut_Tree, QAQ 关键配置: N=205003 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 说明:freopen("123.txt","r",stdin); 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 87 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
#define LL long long
using namespace std;
const int N=205003;
int n,m,x,y,z,id,ans,id_O,v[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
struct Link_Cut_Tree{
	#define pl tr[p].ps[0]
	#define pr tr[p].ps[1]
	#define pf tr[p].fa
	int Q[N];
	struct QAQ{int fa,mx,mxw,tag,ps[2];}tr[N];
	inline void pushup(Re p){
		tr[p].mx=v[p],tr[p].mxw=p;
		if(pl&&tr[pl].mx>tr[p].mx)tr[p].mx=tr[pl].mx,tr[p].mxw=tr[pl].mxw;
		if(pr&&tr[pr].mx>tr[p].mx)tr[p].mx=tr[pr].mx,tr[p].mxw=tr[pr].mxw;
	}
	inline void updata(Re p){swap(pl,pr),tr[p].tag^=1;}
	inline void pushdown(Re p){
		if(tr[p].tag){
			if(pl)updata(pl);
			if(pr)updata(pr);
			tr[p].tag=0;
		}
	}
	inline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}
	inline int which(Re p){return tr[pf].ps[1]==p;}
	inline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}
	inline void rotate(Re p){
		Re fa=pf,fas=which(p);
		Re pa=tr[fa].fa,pas=which(fa);
		Re x=tr[p].ps[fas^1];
		if(nort(fa))tr[pa].ps[pas]=p;pf=pa;
		connect(x,fa,fas),connect(fa,p,fas^1);
		pushup(fa),pushup(p);
	}
	inline void splay(Re p){
		Re x=p,t=0;Q[++t]=x;
		while(nort(x))Q[++t]=x=tr[x].fa;
		while(t)pushdown(Q[t--]);
		for(Re fa;nort(p);rotate(p))
			if(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);
	}
	inline void access(Re p){
		for(Re son=0;p;son=p,p=pf)
			splay(p),pr=son,pushup(p);
	}
	inline void makeroot(Re p){access(p),splay(p),updata(p);}
	inline int findroot(Re p){
		access(p),splay(p),pushdown(p);
		while(pl)pushdown(p=pl);
		return p;
	}
	inline void split(Re x,Re y){makeroot(x),access(y),splay(y);}
	inline void link(Re x,Re y){makeroot(x);if(findroot(y)!=x)tr[x].fa=y;}
	inline void cut(Re x,Re y){
		makeroot(x);
		if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ps[1])
			tr[x].fa=tr[y].ps[0]=0,pushup(y);
	}
	inline int judge(Re x,Re y){makeroot(x);return findroot(y)==x;}
	inline void sakura(Re x,Re y,Re z,Re id){
		if(!judge(x,y))link(x,id),link(id,y),ans+=z;
		else{
			split(x,y);Re mx=tr[y].mx,mxw=tr[y].mxw;
			if(z<mx){
				ans+=z-mx,splay(mxw);
				tr[tr[mxw].ps[0]].fa=tr[tr[mxw].ps[1]].fa=0;
				link(x,id),link(id,y);
			}
		}
	}
}LCT;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	while(m--)in(x),in(y),in(z),v[id=++id_O+n]=z,LCT.sakura(x,y,z,id);
	printf("%d\n",ans);
}
最小生成树 Prim n^2 3.3.2 最小生成树
31 行
CPP JSON
【最小生成树(Prim n^2)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void Prim(无参数) — Prim最小生成树 关键配置: N=5003,M=2e5+3,inf=2e9 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 30 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3,inf=2e9;
int n,x,y,z,T,ans,pan[N],dis[N],a[N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void Prim(){
	for(Re i=0;i<=n;++i)dis[i]=inf;
	Re t=0;dis[1]=0;
	for(Re i=1;i<=n&&t<n;++i){
		Re w=0;
		for(Re j=1;j<=n;++j)if(!pan[j]&&dis[j]<dis[w])w=j;
		pan[w]=1,ans+=dis[w],++t;
		for(Re j=1;j<=n;++j)if(!pan[j])dis[j]=min(dis[j],a[w][j]);
	}
}
int main(){
	in(n),in(T);
	memset(a,127,sizeof(a));
	while(T--)in(x),in(y),in(z),a[x][y]=a[y][x]=min(a[x][y],z);
	Prim();
	printf("%d\n",ans);
}
最小生成树 Prim 3.3.2 最小生成树
35 行
CPP JSON
【最小生成树(Prim)】 最小生成树(MST)算法模板,使用 Kruskal/Prim 算法。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void Prim(无参数) — Prim最小生成树 核心结构体:QAQ, QWQ 关键配置: N=5003,M=2e5+3,inf=2e9 复杂度:O(E log E)(Kruskal),O(V² / E log V)(Prim) 适用场景:连通图的最小代价连接、瓶颈路问题
C++ 34 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=2e5+3,inf=2e9;
int x,y,z,n,m,o,ans,pan[N],dis[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,d;inline bool operator<(QWQ o)const{return d>o.d;};};
priority_queue<QWQ>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void Prim(){
	for(Re i=0;i<=n;++i)pan[i]=0,dis[i]=inf;
	Re t=0;Q.push((QWQ){1,dis[1]=0});
	while(!Q.empty()&t<n){
		Re x=Q.top().x;Q.pop();
		if(pan[x])continue;
		pan[x]=1,++t,ans+=dis[x];
		for(Re i=head[x],to;i;i=a[i].next)
			if(dis[to=a[i].to]>a[i].w)Q.push((QWQ){to,dis[to]=a[i].w});
	}
}
int main(){
	in(n),in(m);
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
	Prim();
	printf("%d",ans);
}
拓扑排序 add 3.3.3 图的连通性
31 行
CPP JSON
【拓扑排序】 拓扑排序模板,基于 Kahn 算法或 DFS。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 核心结构体:QAQ 关键配置: N=5003,M=5e5+3,inf=2e9,P=80112002 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 30 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=5e5+3,inf=2e9,P=80112002;
int n,m,x,y,o,ans,dp[N],ru[N],chu[N],head[N];
struct QAQ{int to,next;}a[M];queue<int>Q;
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}

int main(){
	in(n),in(m);
	while(m--)in(x),in(y),add(x,y),++ru[y],++chu[x];
	for(Re i=1;i<=n;++i)if(!ru[i])dp[i]=1,Q.push(i);
	while(!Q.empty()){
		Re x=Q.front();Q.pop();
		for(Re i=head[x],to;i;i=a[i].next){
			(dp[to=a[i].to]+=dp[x])%=P;
			if(!--ru[to])Q.push(to);
		}
	}
	for(Re i=1;i<=n;++i)if(!chu[i])(ans+=dp[i])%=P;
	printf("%d\n",ans%P);
}
44 行
CPP JSON
【2-SAT(kosaraju)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs1(Re x) — 深度优先搜索遍历 void dfs2(Re x) — 深度优先搜索遍历 void kosaraju(无参数) — 后缀数组 核心结构体:Kosaraju, QAQ 关键配置: N=2e6+3,M=2e6+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 43 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=2e6+3,M=2e6+3;
int n,m,mm,p1,p2,x1,x2,Q_o,X[M],Y[M],ip[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Kosaraju{
	int o,ndfn_o,nQ[N],pan[N],head[N];
	struct QAQ{int x,to,next;}a[M];
	inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs1(Re x){
		pan[x]=1;
		for(Re i=head[x];i;i=a[i].next)if(!pan[a[i].to])dfs1(a[i].to);
		nQ[++ndfn_o]=x;
	}
	inline void dfs2(Re x){
		ip[x]=Q_o;
		for(Re i=head[x];i;i=a[i].next)if(!ip[a[i].to])dfs2(a[i].to);
	}
	inline void kosaraju(){
		for(Re i=1;i<=m;++i)add(X[i],Y[i]);
		for(Re i=1;i<=2*n;++i)if(!pan[i])dfs1(i);
		memset(head,0,sizeof(head));
		memset(pan,0,sizeof(pan));
		memset(a,0,sizeof(a));o=0;
		for(Re i=1;i<=m;++i)add(Y[i],X[i]);
		for(Re i=ndfn_o;i;--i)if(!ip[nQ[i]])++Q_o,dfs2(nQ[i]);
	}
}T1;
int main(){
	in(n),in(mm);
	while(mm--)in(p1),in(x1),in(p2),in(x2),X[++m]=p1+(x1^1)*n,Y[m]=p2+x2*n,X[++m]=p2+(x2^1)*n,Y[m]=p1+x1*n;
	T1.kosaraju();
	for(Re i=1;i<=n;++i)if(ip[i]==ip[i+n])return !printf("IMPOSSIBLE");
	puts("POSSIBLE");
	for(Re i=1;i<=n;++i)printf("%d ",ip[i]<ip[i+n]);
}
40 行
CPP JSON
【2-SAT(tarjan)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 int min(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x) — Tarjan算法(求SCC/LCA/割点桥) void SuoPoint(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ 关键配置: N=2e6+3,M=2e6+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 40 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=2e6+3,M=2e6+3;
int n,m,p1,p2,x1,x2,Q_o,ip[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Tarjan{
	int o,t,dfn_o,Q[N],low[N],dfn[N],pan[N],head[N];
	struct QAQ{int to,next;}a[M];
	inline int min(Re a,Re b){return a<b?a:b;}
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x){
		low[x]=dfn[x]=++dfn_o,Q[++t]=x,pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
			else if(pan[to])low[x]=min(low[x],dfn[to]);
		if(low[x]==dfn[x]){
			++Q_o;
			while(1){
				ip[Q[t]]=Q_o,pan[Q[t]]=0;
				if(x==Q[t--])break;
			}
		}
	}
	inline void SuoPoint(){for(Re i=1;i<=2*n;++i)if(!dfn[i])tarjan(i);}
}T1;
int main(){
	in(n),in(m);
	while(m--)in(p1),in(x1),in(p2),in(x2),T1.add(p1+(x1^1)*n,p2+x2*n),T1.add(p2+(x2^1)*n,p1+x1*n);
	T1.SuoPoint();
	for(Re i=1;i<=n;++i)if(ip[i]==ip[i+n])return !printf("IMPOSSIBLE");
	puts("POSSIBLE");
	for(Re i=1;i<=n;++i)printf("%d ",ip[i]>ip[i+n]);
}
割点 tanjan min 3.3.3 图的连通性
39 行
CPP JSON
【割点 tanjan】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 int min(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x,Re root) — Tarjan算法(求SCC/LCA/割点桥) void cut_point(无参数) — 核心算法函数 核心结构体:Cut_Point, QAQ 关键配置: N=2e4+3,M=2e5+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=2e4+3,M=2e5+3;
int n,m,x,y,ans,cut[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Cut_Point{
	int o,dfn_o,low[N],dfn[N],head[N];
	struct QAQ{int to,next;}a[M];
	inline int min(Re a,Re b){return a<b?a:b;}
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x,Re root){
		Re son=0;dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,root),++son;
				low[x]=min(low[x],low[to]);
				cut[x]|=(x!=root&&low[to]>=dfn[x]);
			}
			else low[x]=min(low[x],dfn[to]);
		cut[x]|=(x==root&&son>1),ans+=cut[x];
	}
	inline void cut_point(){
		for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,i);
	}
}T1;
int main(){
	in(n),in(m);
	while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	T1.cut_point();
	printf("%d\n",ans);
	for(Re i=1;i<=n;++i)if(cut[i])printf("%d ",i);
}
割边,桥 旅游航道 3.3.3 图的连通性
45 行
CPP JSON
【割边,桥(旅游航道)】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void CL(无参数) — 核心算法函数 void tarjan(Re x,Re p) — Tarjan算法(求SCC/LCA/割点桥) void get_bridg(无参数) — 获取值 核心结构体:Tarjan, QAQ 关键配置: N=3e4+3,M=3e4+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 44 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=3e4+3,M=3e4+3;
int n,m,x,y,ans;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Tarjan{
	int o,dfn_o,dfn[N],low[N],head[N],bridge[M<<1];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void CL(){
		memset(bridge,0,sizeof(bridge));
		memset(head,0,sizeof(head));
		memset(low,0,sizeof(low));
		memset(dfn,0,sizeof(dfn));
		dfn_o=ans=0,o=1;
	}
	inline void tarjan(Re x,Re p){
		dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,i);
				low[x]=min(low[x],low[to]);
				if(low[to]>dfn[x])bridge[i]=bridge[i^1]=1,++ans;
			}
			else if(i!=(p^1))low[x]=min(low[x],dfn[to]);
	}
	inline void get_bridg(){for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,-1);}
}T1;
int main(){
    while(scanf("%d%d",&n,&m)&&n&&m){
	    T1.CL();
	    while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
	    T1.get_bridg();
	    printf("%d\n",ans);
    }
}
欧拉回路 (Hierholzer) 无向+有向 3.3.3 图的连通性
63 行
CPP JSON
【欧拉回路 (Hierholzer)(无向+有向)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 void add(Re x,Re y) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 void sakura(无参数) — 后缀数组 核心结构体:Euler_Circle__Undirected_Graph, QAQ, Euler_Circle__Directed_Graph, QAQ 关键配置: N=1e5+3,M=2e5+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
const int N=1e5+3,M=2e5+3;
int n,m,x,y,m_,op;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Euler_Circle__Undirected_Graph{// 无向图欧拉路
	int o,du[N],cur[N],ans[M],pan[M<<1],head[N];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x){
		for(Re i=head[x];i;i=head[x]){
			head[x]=a[i].next;// 当前弧优化
			if(!pan[i]){
				pan[i]=pan[i^1]=1;
				dfs(a[i].to);
				ans[++ans[0]]=(i&1)?-i/2:i/2;
			}
		}
	}
	inline void sakura(){
		in(n),in(m),m_=m,o=1;
		while(m_--)in(x),in(y),add(x,y),add(y,x),++du[x],++du[y];
		for(Re i=1;i<=n;cur[i]=head[i],++i)if(du[i]&1){puts("NO");return;}
		for(Re i=1;i<=n;++i)if(du[i]){dfs(i);break;}
		if(ans[0]!=m){puts("NO");return;}
		puts("YES");
		for(Re i=ans[0];i>=1;--i)printf("%d ",ans[i]);
	}
}T1;
struct Euler_Circle__Directed_Graph{// 无向图欧拉路
	int o,ru[N],chu[N],cur[N],ans[M],head[N];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x){
		for(Re i=head[x];i;i=head[x]){
			head[x]=a[i].next;// 当前弧优化
			dfs(a[i].to);
			ans[++ans[0]]=i;
		}
	}
	inline void sakura(){
		in(n),in(m),m_=m;
		while(m_--)in(x),in(y),add(x,y),++ru[y],++chu[x];
		for(Re i=1;i<=n;cur[i]=head[i],++i)if(ru[i]!=chu[i]){puts("NO");return;}
		for(Re i=1;i<=n;++i)if(chu[i]){dfs(i);break;}
		if(ans[0]!=m){puts("NO");return;}
		puts("YES");
		for(Re i=ans[0];i>=1;--i)printf("%d ",ans[i]);
	}
}T2;
int main(){
	in(op);
	if(op==1)T1.sakura();
	if(op==2)T2.sakura();
}
欧拉路,欧拉回路 骑马修栅栏 3.3.3 图的连通性
29 行
CPP JSON
【欧拉路,欧拉回路(骑马修栅栏)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 void dfs(Re x) — 深度优先搜索遍历 关键配置: N=1030 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 28 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=1030;
int n,x,y,mi=2e9,st=2e9,as,du[N],ans[N],r[N][N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void dfs(Re x){
	for(Re i=1;i<=500;++i)
		if(r[x][i]){
			--r[x][i],--r[i][x];
			dfs(i);
		}
	ans[++as]=x;
}
int main(){
	in(n);
	for(Re i=1;i<=n;++i)in(x),in(y),++r[x][y],++r[y][x],++du[x],++du[y],mi=min(mi,min(x,y));
	for(Re i=1;i<=500;++i)if(du[i]&1)st=min(st,i);
	if(st==2e9)st=mi;
	dfs(st);
	for(Re i=as;i;--i)printf("%d\n",ans[i]);
}
缩点—强联通分量 Kosaraju 3.3.3 图的连通性
67 行
CPP JSON
【缩点—强联通分量(Kosaraju)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void dfs1(Re x) — 深度优先搜索遍历 void dfs2(Re x) — 深度优先搜索遍历 void kosaraju(无参数) — 后缀数组 void add(Re x,Re y) — 加法更新 void creat(无参数) — 核心算法函数 核心结构体:Kosaraju, QAQ, Tuopu, QAQ 关键配置: N=1e6+3,M=1e6+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 66 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
const int N=1e6+3,M=1e6+3;
int n,m,Q_o,ans,X[M],Y[M],A[N],ip[N],gs[N],dp[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
struct Kosaraju{
	int o,ndfn_o,nQ[N],pan[N],head[N];
	struct QAQ{int x,to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs1(Re x){
		pan[x]=1;
		for(Re i=head[x];i;i=a[i].next)if(!pan[a[i].to])dfs1(a[i].to);
		nQ[++ndfn_o]=x;
	}
	inline void dfs2(Re x){
		ip[x]=Q_o,gs[Q_o]+=A[x];
		for(Re i=head[x];i;i=a[i].next)if(!ip[a[i].to])dfs2(a[i].to);
	}
	inline void kosaraju(){
		for(Re i=1;i<=m;++i)add(X[i],Y[i]);
		for(Re i=1;i<=n;++i)if(!pan[i])dfs1(i);
		memset(head,0,sizeof(head));
		memset(pan,0,sizeof(pan));
		memset(a,0,sizeof(a));o=0;
		for(Re i=1;i<=m;++i)add(Y[i],X[i]);
		for(Re i=ndfn_o;i;--i)if(!ip[nQ[i]])++Q_o,dfs2(nQ[i]);
	}
}T1;
struct Tuopu{
	int o,x,y,ru[N],pan[N],head[N];std::queue<int>Q;
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void creat(){
		for(Re i=1;i<=T1.o;++i)
			if((x=ip[T1.a[i].x])!=(y=ip[T1.a[i].to]))
				++ru[y],add(x,y);
	}
	inline void tuopu(){
		creat();
		for(Re i=1;i<=Q_o;++i)if(!ru[i])dp[i]=gs[i],Q.push(i);
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			for(Re i=head[x],to;i;i=a[i].next){
				to=a[i].to;
				dp[to]=max(dp[to],dp[x]+gs[to]);
				if(!(--ru[to]))Q.push(to);
			}
		}
	}
}T2;
int main(){
	in(n),in(m);
	for(Re i=1;i<=n;++i)in(A[i]);
	for(Re i=1;i<=m;++i)in(X[i]),in(Y[i]);
	T1.kosaraju(),T2.tuopu();
	for(Re i=1;i<=Q_o;++i)ans=max(ans,dp[i]);
	printf("%d",ans);
}
缩点—强联通分量 Tarjan 3.3.3 图的连通性
63 行
CPP JSON
【缩点—强联通分量(Tarjan)】 图的连通性相关算法模板。 核心函数: void in(Re &x) — 核心算法函数 int min(Re a,Re b) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x) — Tarjan算法(求SCC/LCA/割点桥) void SuoPoint(无参数) — 核心算法函数 void add(Re x,Re y) — 加法更新 void creat(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ, Tuopu, QAQ 关键配置: N=1e4+3,M=1e5+3 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 62 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
const int N=1e4+3,M=1e5+3;
int n,m,x,y,Q_o,ans,A[N],ru[N],gs[N],ip[N],dp[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int min(Re a,Re b){return a<b?a:b;}
inline int max(Re a,Re b){return a>b?a:b;}
struct Tarjan{
	int o,t,dfn_o,Q[N],low[N],dfn[N],pan[N],head[N];
	struct QAQ{int x,to,next;}a[M];
	inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x){
		dfn[x]=low[x]=++dfn_o,Q[++t]=x,pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
			else if(pan[to])low[x]=min(low[x],dfn[to]);
		if(low[x]==dfn[x]){
			++Q_o;
			while(1){
				ip[Q[t]]=Q_o,gs[Q_o]+=A[Q[t]],pan[Q[t]]=0;
				if(x==Q[t--])break;
			}
		}
	}
	inline void SuoPoint(){for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);}
}T1;
struct Tuopu{
	int o,ru[N],pan[N],head[N];std::queue<int>Q;
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void creat(){
		for(Re i=1;i<=T1.o;++i)
			if((x=ip[T1.a[i].x])!=(y=ip[T1.a[i].to]))
				++ru[y],add(x,y);
	}
	inline void tuopu(){
		for(Re i=1;i<=Q_o;++i)if(!ru[i])dp[i]=gs[i],Q.push(i);
		while(!Q.empty()){
			Re x=Q.front();Q.pop();
			for(Re i=head[x],to;i;i=a[i].next){
				to=a[i].to;
				dp[to]=max(dp[to],dp[x]+gs[to]);
				if(!(--ru[to]))Q.push(to);
			}
		}
	}
}T2;
int main(){
	in(n),in(m);
	for(Re i=1;i<=n;++i)in(A[i]);
	while(m--)in(x),in(y),T1.add(x,y);
	T1.SuoPoint(),T2.creat(),T2.tuopu();
	for(Re i=1;i<=Q_o;++i)ans=max(ans,dp[i]);
	printf("%d",ans);
}
缩点—点双连通分量 矿场搭建 3.3.3 图的连通性
65 行
CPP JSON
【缩点—点双连通分量(矿场搭建)】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 int max(Re a,Re b) — 核心算法函数 void add(Re x,Re y) — 加法更新 void CL(无参数) — 核心算法函数 void tarjan(Re x,Re rt) — Tarjan算法(求SCC/LCA/割点桥) void SuoPoint(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ 关键配置: N=1003,M=503 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 64 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,M=503;
int n,m,x,y,T,Q_o,tmp,ans1,cut[N];LL ans2;
std::vector<int>dcc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
struct Tarjan{
	int o,t,dfn_o,Q[N],dfn[N],low[N],head[N];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void CL(){
		memset(head,0,sizeof(head));
		memset(low,0,sizeof(low));
		memset(dfn,0,sizeof(dfn));
		memset(cut,0,sizeof(cut));
		dfn_o=t=o=0;
	}
	inline void tarjan(Re x,Re rt){
		Re son=0;Q[++t]=x,dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,rt),++son;
				low[x]=min(low[x],low[to]);
				if(low[to]>=dfn[x]){
					if(x!=rt)cut[x]=1;
					else cut[x]|=son>1;
					++Q_o;
					while(1){
						dcc[Q_o].push_back(Q[t]);
						if(to==Q[t--])break;
					}
					dcc[Q_o].push_back(x);
				}
			}
			else low[x]=min(low[x],dfn[to]);
	}
	inline void SuoPoint(){for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,i);}
}T1;
int main(){
    while(scanf("%d",&m)&&m){
	    for(Re i=1;i<=Q_o;++i)dcc[i].clear();
	    T1.CL(),Q_o=ans1=n=0,ans2=1;
	    while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x),n=max(n,max(x,y));
	    T1.SuoPoint();
	    for(Re i=1;i<=Q_o;++i){
	    	tmp=0,n=dcc[i].size();
	    	for(Re j=0;j<n;++j)tmp+=cut[dcc[i][j]];
	    	if(!tmp)ans1+=2,ans2*=(n-1)*n/2;
	    	else if(tmp<2)ans1+=1,ans2*=(n-1);
	    }
	    printf("Case %d: %d %lld\n",++T,ans1,ans2);
    }
}
缩点—边双连通分量 Redundant Paths 3.3.3 图的连通性
46 行
CPP JSON
【缩点—边双连通分量(Redundant Paths)】 无向图的割点/桥与双连通分量模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 void tarjan(Re x,Re p) — Tarjan算法(求SCC/LCA/割点桥) void dfs(Re x) — 深度优先搜索遍历 void SuoPoint(无参数) — 核心算法函数 核心结构体:Tarjan, QAQ 关键配置: N=5003,M=10003 适用场景:SCC缩点、2-SAT建图、割点/桥识别
C++ 45 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=5003,M=10003;
int n,m,x,y,Q_o,leaf,ip[N],du[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Tarjan{
	int o,dfn_o,dfn[N],low[N],head[N],bridge[M<<1];
	struct QAQ{int to,next;}a[M<<1];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void tarjan(Re x,Re p){
		dfn[x]=low[x]=++dfn_o;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to]){
				tarjan(to,i);
				low[x]=min(low[x],low[to]);
				if(low[to]>dfn[x])bridge[i]=bridge[i^1]=1;
			}
			else if(i!=(p^1))low[x]=min(low[x],dfn[to]);
	}
	inline void dfs(Re x){
		ip[x]=Q_o;
		for(Re i=head[x];i;i=a[i].next)
			if(!ip[a[i].to]&&!bridge[i])dfs(a[i].to);
	}
	inline void SuoPoint(){
		for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i,-1);
		for(Re i=1;i<=n;++i)if(!ip[i])++Q_o,dfs(i);
	}
}T1;
int main(){
    in(n),in(m),T1.o=1;
    while(m--)in(x),in(y),T1.add(x,y),T1.add(y,x);
    T1.SuoPoint();
    for(Re i=2;i<=T1.o;i+=2)
    	if((x=ip[T1.a[i].to])!=(y=ip[T1.a[i^1].to]))++du[x],++du[y];
    for(Re i=1;i<=Q_o;++i)leaf+=(du[i]==1);
    printf("%d",leaf+1>>1);
}
二分图最大匹配-匈牙利算法 erfentu 3.3.4 二分图与最大匹配
34 行
CPP JSON
【二分图最大匹配——匈牙利算法(Hungarian Algorithm)】 ▪ main() — 读入左右部节点数 n1,n2 和边数 m,用 lambda 递归 DFS 寻找增广路 ▪ dfs(self, x) — 嵌套 DFS:对左部节点 x 尝试匹配,遍历其所有邻接右部节点 y:若 y 未被访问且(y 未匹配 或 y 的当前匹配者可换人),则 match[y]=x 并返回 true ▪ vis[] — 每轮 DFS 的访问标记数组,防止重复访问右部节点 ▪ match[] — 右部节点当前的匹配对象(0 表示未匹配) 时间复杂度 O(VE)。适用于任务分配、人员配对、棋盘多米诺覆盖等二分图匹配模型。
C++ 34 行 CPP
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n1,n2,m;
    cin >> n1 >> n2 >> m;
    vector<vector<int>>ver(n1+1);
    for(int i = 1;i <= m;i++){
        int x,y;
        cin >> x >> y;
        ver[x].push_back(y);
    }

    int ans = 0;
    vector<int>match(n2+1);
    for(int i = 1;i <= n1;i++){
        vector<int>vis(n2+1);
        auto dfs = [&](auto self,int x) -> bool {
            for(auto y : ver[x]){
                if(vis[y])continue;
                vis[y] = 1;
                if(!match[y] || self(self,match[y])){
                    match[y] = x;
                    return true;
                }
            }
            return false;
        };
        if(dfs(dfs,i)){
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}
二分图—最大匹配 add 3.3.4 二分图与最大匹配
36 行
CPP JSON
【二分图—最大匹配】 二分图匹配算法模板(匈牙利算法 / Hopcroft-Karp)。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y) — 加法更新 int dfs(Re x) — 深度优先搜索遍历 核心结构体:QAQ 关键配置: N=1003 适用场景:二分图判定与匹配、棋盘覆盖模型、最小点覆盖
C++ 35 行 CPP
#include<cstring>
#include<cstdio>
#define Re register int
const int N=1003;
int o,n,m,e,x,y,ans,pan[N],head[N],match[N];
struct QAQ{int to,next;}a[N*N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline int dfs(Re x){
	for(Re i=head[x],to;i;i=a[i].next)
		if(!pan[to=a[i].to]){
			pan[to]=1;
			if(!match[to]||dfs(match[to])){
				match[to]=x;return 1;
			}
		}
	return 0;
}
int main(){
	in(n),in(m),in(e);
	while(e--){
		in(x),in(y);
		if(x<=n&&y<=m)add(x,y);
	}
	for(Re i=1;i<=n;++i){
		memset(pan,0,sizeof(pan));
		ans+=dfs(i);
	}
	printf("%d",ans);
}
二分图判定 染色法 3.3.4 二分图与最大匹配
40 行
CPP JSON
【二分图判定(染色法)】 二分图匹配算法模板(匈牙利算法 / Hopcroft-Karp)。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 int judge(无参数) — 判定函数 核心结构体:QAQ 关键配置: N=2003,M=1e6+3 适用场景:二分图判定与匹配、棋盘覆盖模型、最小点覆盖
C++ 39 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=2003,M=1e6+3;
int n,m,x,y,h,t,o,T,O,Q[N],head[N],color[N];
struct QAQ{int to,next;}a[M<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int judge(){
	for(Re i=1;i<=n;++i)
		if(!color[i]){
			h=1,t=0,Q[++t]=i,color[i]=1;
			while(h<=t){
				Re x=Q[h++];
				for(Re j=head[x],to;j;j=a[j].next)
					if(!color[to=a[j].to])color[to]=3-color[x],Q[++t]=to;
					else if(color[to]==color[x])return 0;
			}
		}
	return 1;
}
int main(){
	in(T);
	while(T--){
		memset(color,0,sizeof(color));
		memset(head,0,sizeof(head));
		in(n),in(m),o=0;
		while(m--)in(x),in(y),add(x,y),add(y,x);
		printf("Scenario #%d:\n",++O);
		puts(judge()?"No suspicious bugs found!\n":"Suspicious bugs found!\n");
	}
}
网络流-最大流与最小割 wangluoliu 3.3.5 网络流
101 行
CPP JSON
【网络流——最大流与最小割(Dinic 算法)】 ▪ addEdge(from, to, cap) — 添加有向边及其反向边(cap=0),记录 rev 索引用于残量更新 ▪ bfs(s, t) — BFS 构建层次图(level 数组):从源点 s 出发,沿 cap>0 的边走,标记各节点层次 ▪ dfs(v, t, upTo) — DFS 多路增广:在层次图上从 v 向 t 推进,最多增广 upTo 流量;使用 iter[] 当前弧优化避免重复走死路 ▪ maxFlow(s, t) — Dinic 主函数:反复 bfs()+dfs() 直到无法到达汇点,累计流量 ▪ getMinCutEdges(s) — 从源点 BFS(只走 cap>0 边),可达节点与不可达节点间的边即为最小割边集 一般图 O(V²E),二分图匹配 O(E√V)。含割边标记 is_cut。适用于最大流、最小割、二分图匹配。
C++ 101 行 CPP
struct Edge {
    int to, rev;
    int cap;
    bool is_cut; // 标记是否为割边
};

class MinCut {
private:
    std::vector<Edge> G[MAXN];
    int level[MAXN];
    int iter[MAXN];

public:
    // 添加一条从from到to,容量为cap的边
    void addEdge(int from, int to, int cap) {
        G[from].push_back({to, (int)G[to].size(), cap, false});
        G[to].push_back({from, (int)G[from].size() - 1, 0, false});
    }

    // 构建层次图
    bool bfs(int s, int t) {
        memset(level, -1, sizeof(level));
        std::queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (const auto& e : G[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    // 在层次图上寻找增广路
    int dfs(int v, int t, int upTo) {
        if (v == t) return upTo;
        for (int &i = iter[v]; i < G[v].size(); ++i) {
            Edge &e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                int d = dfs(e.to, t, std::min(upTo, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    // 求最大流
    int maxFlow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            memset(iter, 0, sizeof(iter));
            int f;
            while ((f = dfs(s, t, INF)) > 0) {
                flow += f;
            }
        }
        return flow;
    }

    // 获取最小割的割边集合
    std::vector<std::pair<int, int>> getMinCutEdges(int s) {
        std::vector<std::pair<int, int>> cutEdges;
        bool vis[MAXN] = {0};
        std::queue<int> q;
        q.push(s);
        vis[s] = true;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (const auto& e : G[v]) {
                if (e.cap > 0 && !vis[e.to]) {
                    vis[e.to] = true;
                    q.push(e.to);
                }
            }
        }
        // 割边:从S集合到T集合的满流边
        for (int u = 0; u < MAXN; ++u) {
            if (vis[u]) {
                for (const auto& e : G[u]) {
                    if (!vis[e.to] && G[e.to][e.rev].cap > 0) {
                        cutEdges.emplace_back(u, e.to);
                    }
                }
            }
        }
        return cutEdges;
    }

    // 清空图
    void clear(int n) {
        for (int i = 0; i <= n; ++i) G[i].clear();
    }
};
最大流 (m n^2) Dinic+多路增广+当前弧 3.3.5 网络流
55 行
CPP JSON
【最大流 (m n^2)(Dinic+多路增广+当前弧)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add_(Re x,Re y,Re flow) — 加法更新 void add(Re x,Re y,Re flow) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void dinic(Re st,Re ed) — 核心算法函数 核心结构体:Dinic, QAQ 关键配置: N=1e4+5,M=1e5+5,inf=2147483647 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 54 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e4+5,M=1e5+5,inf=2147483647;
int x,y,z,n,m,s,t,st,ed;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Dinic{
	int o,h,t,Q[N],dis[N],cur[N],head[N];LL maxflow;
	Dinic(){o=1;}
	struct QAQ{int to,next,flow;}a[M<<1];
	inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
	inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
	inline int bfs(Re st,Re ed){
		for(Re i=0;i<=ed;++i)dis[i]=0,cur[i]=head[i];
		h=1,t=0,Q[++t]=st,dis[st]=1;
		while(h<=t){
			Re x=Q[h++];
			for(Re i=head[x],to;i;i=a[i].next)
				if(a[i].flow&&!dis[to=a[i].to]){
					dis[to]=dis[x]+1,Q[++t]=to;
					if(to==ed)return 1;
				}
		}
		return 0;
	}
	inline int dfs(Re x,Re flow){
		if(x==ed||!flow)return flow;
		Re tmp=0,to,f;
		for(Re i=cur[x];i;i=a[i].next){
			cur[x]=i;
			if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
				a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
				if(flow==tmp)break;
			}
		}
		return tmp;
	}
	inline void dinic(Re st,Re ed){while(bfs(st,ed))maxflow+=dfs(st,inf);}
}T1;
int main(){
    in(n),in(m),in(s),in(t),st=n+1,ed=st+1;
    while(m--)in(x),in(y),in(z),T1.add(x,y,z);
    T1.add(st,s,inf),T1.add(t,ed,inf),T1.dinic(st,ed);
    printf("%lld",T1.maxflow);
}
最大流 (n m^2) EK 3.3.5 网络流
48 行
CPP JSON
【最大流 (n m^2)(EK)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 void EK(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=1e4+3,M=1e5+3,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 47 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+3,M=1e5+3,inf=2e9;
int x,y,z,o=1,n,m,h,t,st,ed,Q[N],cyf[N],pan[N],pre[N],head[N];long long maxflow; 
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){
	for(Re i=0;i<=n;++i)pan[i]=0;
	h=1,t=0,pan[st]=1,Q[++t]=st,cyf[st]=inf;
	while(h<=t){
		Re x=Q[h++];
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&!pan[to=a[i].to]){
				cyf[to]=min(cyf[x],a[i].flow);
				Q[++t]=to,pre[to]=i,pan[to]=1;
				if(to==ed)return 1;
			}
	}
	return 0;
}
inline void EK(Re st,Re ed){
	while(bfs(st,ed)==1){
		Re x=ed;maxflow+=cyf[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
int main(){
	in(n),in(m),in(st),in(ed);
	while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,0);
	EK(st,ed);
	printf("%lld",maxflow);
}
最小割可行边、必须边 add_ 3.3.5 网络流
75 行
CPP JSON
【最小割可行边、必须边】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add_(Re x,Re y,Re flow) — 加法更新 void add(Re x,Re y,Re flow) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void tarjan(Re x) — Tarjan算法(求SCC/LCA/割点桥) void sakura(无参数) — 后缀数组 核心结构体:Dinic, QAQ 关键配置: N=4003,M=6e4+3,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 说明:freopen("123.txt","r",stdin); 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=4003,M=6e4+3,inf=2e9;
int n,m,x,y,z,st,ed;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Dinic{
	int o,h,t,Q[N],dis[N],cur[N],head[N];
	struct QAQ{int to,next,flow;}a[M<<1];
	inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
	inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
	inline int bfs(Re st,Re ed){
		for(Re i=0;i<=n;++i)dis[i]=0,cur[i]=head[i];
		h=1,t=0,dis[st]=1,Q[++t]=st;
		while(h<=t){
			Re x=Q[h++];
			for(Re i=head[x],to;i;i=a[i].next)
				if(a[i].flow&&!dis[to=a[i].to]){
					dis[to]=dis[x]+1,Q[++t]=to;
					if(to==ed)return 1;
				}
		}
		return 0;
	}
	inline int dfs(Re x,Re flow){
		if(x==ed||!flow)return flow;
		Re tmp=0,to,f;
		for(Re i=cur[x];i;i=a[i].next){
			cur[x]=i;
			if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
				a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
				if(flow==tmp)break;
			}
		}
		return tmp;
	}
	int Q_o,dfn_O,ip[N],dfn[N],low[N],pan[N];
	inline void tarjan(Re x){
		dfn[x]=low[x]=++dfn_O,Q[++t]=x,pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow){
				if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
				else if(pan[to])low[x]=min(low[x],dfn[to]);
			}
		if(dfn[x]==low[x]){
			++Q_o;
			while(1){
				ip[Q[t]]=Q_o,pan[Q[t]]=0;
				if(x==Q[t--])break;
			}
		}
	}
	inline void sakura(){
		while(bfs(st,ed))dfs(st,inf);
		for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);
		for(Re i=2;i<=o;i+=2)printf("%d %d\n",
			(!a[i].flow&&ip[a[i^1].to]!=ip[a[i].to]),
			(!a[i].flow&&ip[st]==ip[a[i^1].to]&&ip[a[i].to]==ip[ed]));
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(st),in(ed),T1.o=1;
	while(m--)in(x),in(y),in(z),T1.add(x,y,z);
	T1.sakura();
}
最小费用最大流 EK+SPFA 3.3.5 网络流
54 行
CPP JSON
【最小费用最大流(EK+SPFA)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add_(Re x,Re y,Re flow,Re w) — 加法更新 void add(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 核心结构体:MCMF, QAQ 关键配置: N=5005,M=5e4+5,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 说明:freopen("123.txt","r",stdin); 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 53 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5005,M=5e4+5,inf=2e9;
int x,y,z,w,n,m,s,t,st,ed;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct MCMF{
	int o,h,t,cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost,maxflow;
	MCMF(){o=1;}
	struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
	inline void add_(Re x,Re y,Re flow,Re w){a[++o].w=w,a[o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
	inline void add(Re a,Re b,Re flow,Re w){add_(a,b,flow,w),add_(b,a,0,-w);}
	inline int SPFA(Re st,Re ed){
		for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
		Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
		while(!Q.empty()){
			Re x=Q.front();Q.pop();pan[x]=0;
			for(Re i=head[x],to;i;i=a[i].next)
				if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
					dis[to]=dis[x]+a[i].w,pre[to]=i;
					cyf[to]=min(cyf[x],a[i].flow);
					if(!pan[to])pan[to]=1,Q.push(to);
				}
		}
		return dis[ed]!=inf;
	}
	inline void EK(Re st,Re ed){
		while(SPFA(st,ed)){
			Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
			while(x!=st){
				Re i=pre[x];
				a[i].flow-=cyf[ed];
				a[i^1].flow+=cyf[ed];
				x=a[i^1].to;
			}
		}
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(s),in(t),st=n+1,ed=st+1;
	while(m--)in(x),in(y),in(z),in(w),T1.add(x,y,z,w);
	T1.add(st,s,inf,0),T1.add(t,ed,inf,0),T1.EK(st,ed);
	printf("%lld %lld\n",T1.maxflow,T1.mincost);
}
孤岛营救问题 (EK) MCMF 3.3.5 网络流
101 行
CPP JSON
【孤岛营救问题 (EK)(MCMF)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z,Re w) — 加法更新 void add_(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 int P(Re x,Re y,Re k) — 核心算法函数 核心结构体:QAQ 关键配置: N=2e5,M=2e6+5,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 100 行 CPP
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2e5,M=2e6+5,inf=2e9;
int T,x,y,z,w,G,o=1,p,n,m,h,t,st,ed,maxp,cyf[N],pan[N],pre[N],dis[N],head[N],Map[11][11][11][11];LL mincost,maxflow; 
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;vector<int>key[11][11];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
	Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w,pre[to]=i;
				cyf[to]=min(cyf[x],a[i].flow);
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
	while(SPFA(st,ed)){
		Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
inline int P(Re x,Re y,Re k){return (x-1)*m+y+k*n*m;}
int main(){
	in(n),in(m),in(p),maxp=(1<<p)-1;st=(maxp+1)*n*m+1,ed=st+1;
	in(T);while(T--)in(x),in(y),in(z),in(w),in(G),Map[x][y][z][w]=Map[z][w][x][y]=G?G:-1;
	in(T);while(T--)in(x),in(y),in(G),key[x][y].push_back(G);
	add_(st,P(1,1,0),1,0);
	for(Re k=0;k<=maxp;++k)add_(P(n,m,k),ed,1,0);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			if(!key[i][j].empty())
				for(Re O=0;O<key[i][j].size();++O){
					Re KEY=key[i][j][O];
					for(Re k=0;k<=maxp;++k){
						if(!((k>>KEY-1)&1))add_(P(i,j,k),P(i,j,k|(1<<KEY-1)),inf,0);
						else{
							if(i<n&&Map[i][j][i+1][j]!=-1){
								if(!Map[i][j][i+1][j])add_(P(i,j,k),P(i+1,j,k),inf,1);
								else if((k>>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1);
							}
							if(j<m&&Map[i][j][i][j+1]!=-1){
								if(!Map[i][j][i][j+1])add_(P(i,j,k),P(i,j+1,k),inf,1);
								else if((k>>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1);
							}
							if(i>1&&Map[i][j][i-1][j]!=-1){
								if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1);
								else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1);
							}
							if(j>1&&Map[i][j][i][j-1]!=-1){
								if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1);
								else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1);
							}
						}
					}
				}
			else
				for(Re k=0;k<=maxp;++k){
					if(i<n&&Map[i][j][i+1][j]!=-1){
						if(!Map[i][j][i+1][j])add_(P(i,j,k),P(i+1,j,k),inf,1);
						else if((k>>Map[i][j][i+1][j]-1)&1)add_(P(i,j,k),P(i+1,j,k),inf,1);
					}
					if(j<m&&Map[i][j][i][j+1]!=-1){
						if(!Map[i][j][i][j+1])add_(P(i,j,k),P(i,j+1,k),inf,1);
						else if((k>>Map[i][j][i][j+1]-1)&1)add_(P(i,j,k),P(i,j+1,k),inf,1);
					}
					if(i>1&&Map[i][j][i-1][j]!=-1){
						if(!Map[i][j][i-1][j])add_(P(i,j,k),P(i-1,j,k),inf,1);
						else if((k>>Map[i][j][i-1][j]-1)&1)add_(P(i,j,k),P(i-1,j,k),inf,1);
					}
					if(j>1&&Map[i][j][i][j-1]!=-1){
						if(!Map[i][j][i][j-1])add_(P(i,j,k),P(i,j-1,k),inf,1);
						else if((k>>Map[i][j][i][j-1]-1)&1)add_(P(i,j,k),P(i,j-1,k),inf,1);
					}
				}
	EK(st,ed);
	if(maxflow)printf("%lld",mincost);
	else printf("-1");
}
数字梯形问题 (EK) MCMF 3.3.5 网络流
92 行
CPP JSON
【数字梯形问题 (EK)(MCMF)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z,Re w) — 加法更新 void add_(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 void TAT1(无参数) — 核心算法函数 void TAT2(无参数) — 核心算法函数 void TAT3(无参数) — 核心算法函数 核心结构体:QAQ 关键配置: N=1200,M=1865,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 91 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1200,M=1865,inf=2e9;
int o=1,n,m,h,t,st,ed,O,Poi[23][43],A[23][43],cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow; 
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
    for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
    Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
    while(!Q.empty()){
    	Re x=Q.front();Q.pop();pan[x]=0;
    	for(Re i=head[x],to;i;i=a[i].next)
    		if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){
    			dis[to]=dis[x]+a[i].w,pre[to]=i;
    			cyf[to]=min(cyf[x],a[i].flow);
    			if(!pan[to])pan[to]=1,Q.push(to);
    		}
    }
    return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
    while(SPFA(st,ed)){
    	Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
    	while(x!=st){
    		Re i=pre[x];
    		a[i].flow-=cyf[ed];
    		a[i^1].flow+=cyf[ed];
    		x=a[i^1].to;
    	}
    }
}
inline void TAT1(){
    for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
    for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,1,0);
    for(Re i=1;i<=n;++i)
    	for(Re j=1;j<=m+i-1;++j){
    		add_(Poi[i][j],Poi[i][j]+O,1,A[i][j]);
    		if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],1,0),add_(Poi[i][j]+O,Poi[i+1][j+1],1,0);
    	}
    EK(st,ed);
    printf("%lld\n",maxcost);
}
inline void TAT2(){
    for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
    for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,inf,0);
    for(Re i=1;i<=n;++i)
    	for(Re j=1;j<=m+i-1;++j){
    		add_(Poi[i][j],Poi[i][j]+O,inf,A[i][j]);
    		if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],1,0),add_(Poi[i][j]+O,Poi[i+1][j+1],1,0);
    	}
    EK(st,ed);
    printf("%lld\n",maxcost);
}
inline void TAT3(){
    for(Re i=1;i<=m;++i)add_(st,Poi[1][i],1,0);
    for(Re i=1;i<=m+n-1;++i)add_(Poi[n][i]+O,ed,inf,0);
    for(Re i=1;i<=n;++i)
    	for(Re j=1;j<=m+i-1;++j){
            add_(Poi[i][j],Poi[i][j]+O,inf,A[i][j]);
            if(i<n)add_(Poi[i][j]+O,Poi[i+1][j],inf,0),add_(Poi[i][j]+O,Poi[i+1][j+1],inf,0);
    	}
    EK(st,ed);
    printf("%lld\n",maxcost);
}
inline void CL(){
    memset(head,0,sizeof(head));
    memset(cyf,0,sizeof(cyf));
    memset(pre,0,sizeof(pre));
    memset(a,0,sizeof(a));
    maxflow=maxcost=0,o=1;
}
int main(){
    in(m),in(n);
    for(Re i=1;i<=n;++i)
    	for(Re j=1;j<=m+i-1;++j)
            in(A[i][j]),Poi[i][j]=++O;
    st=O<<1|1,ed=st+1;
    TAT1(),CL(),TAT2(),CL(),TAT3();
}
方格取数问题 Dinic 3.3.5 网络流
66 行
CPP JSON
【方格取数问题(Dinic)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void add_(Re x,Re y,Re z) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void Dinic(Re st,Re ed) — 核心算法函数 int Poi(Re i,Re j) — 核心算法函数 核心结构体:QAQ 关键配置: N=1e4+5,M=3e4+5,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 说明:若边权为0,不满足增广路性质,此时dfs返回值f为0,不必执行下面了 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 66 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=3e4+5,inf=2e9;
int x,n,m,h,t,o=1,T,st,ed,ans,maxflow,Q[N],cur[N],dis[N],head[N],wi[4]={0,0,1,-1},wj[4]={1,-1,0,0};
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re z){add(x,y,z),add(y,x,0);}
inline int bfs(Re st,Re ed){//bfs求源点到所有点的最短路 
    for(Re i=0;i<=ed;++i)cur[i]=head[i],dis[i]=0;//当前弧优化cur=head
    h=1,t=0,dis[st]=1,Q[++t]=st;
    while(h<=t){
        Re x=Q[h++],to;
        for(Re i=head[x];i;i=a[i].next)
            if(a[i].flow&&!dis[to=a[i].to]){
            	dis[to]=dis[x]+1,Q[++t]=to;
            	if(to==ed)return 1;
            }
    }
    return 0;
}
inline int dfs(Re x,Re flow){//flow为源点到x的路径上的最小边权 
    if(!flow||x==ed)return flow;//发现没有流了或者到达终点即可返回 
    Re tmp=0,to,f;
    for(Re i=cur[x];i;i=a[i].next){
    	cur[x]=i;//当前弧优化cur=i
    	if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
    	//若边权为0,不满足增广路性质,此时dfs返回值f为0,不必执行下面了 
            a[i].flow-=f,a[i^1].flow+=f;
            tmp+=f;//记录终点已经有了多少流 
            if(!(flow-tmp))break;//前面那些儿子都是最短路,这些最优路径已经榨干了从x出来的所有流,后面的都不用管了 
    	}
    }
    return tmp;
}
inline void Dinic(Re st,Re ed){
    Re flow=0;maxflow=0;
    while(bfs(st,ed))maxflow+=dfs(st,inf);
}
inline int Poi(Re i,Re j){return (i-1)*m+j;}
int main(){
	in(n),in(m),st=n*m+1,ed=st+1;
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j){
			in(x),ans+=x;
			if((i+j)%2)add_(st,Poi(i,j),x);
			else add_(Poi(i,j),ed,x);
		}
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			if((i+j)%2)for(Re k=0;k<4;++k){
				Re ni=i+wi[k],nj=j+wj[k];
				if(ni>=1&&ni<=n&&nj>=1&&nj<=m)add_(Poi(i,j),Poi(ni,nj),inf);
			}
	Dinic(st,ed);
	printf("%d\n",ans-maxflow);
}
汽车加油行驶问题 (EK) MCMF 3.3.5 网络流
71 行
CPP JSON
【汽车加油行驶问题 (EK)(MCMF)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z,Re w) — 加法更新 void add_(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 int P(Re x,Re y,Re k) — 核心算法函数 核心结构体:QAQ 关键配置: N=11e4+5,M=6e5+5,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 说明:��ÿһ���(n,n)����������㣬����n>=2��������㲻���ܵ����յ㣬��˲��������͵��յ㣬���Ե�0�㲻��;����״̬�����뻨��A���ͼӵ����������ڲ��������͵���ijһ�㣬�������͵ĵ�0����Բ��ӣ�����;������֮��״̬����������״̬����K-1�͵����������ĸ����� 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 70 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=11e4+5,M=6e5+5,inf=2e9;
int x,y,z,w,o=1,n,m,h,t,A,B,C,K,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost,maxflow; 
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
	Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w,pre[to]=i;
				cyf[to]=min(cyf[x],a[i].flow);
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
	while(SPFA(st,ed)){
		Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
inline int P(Re x,Re y,Re k){return (x-1)*n+y+k*n*n;}
int main(){
	in(n),in(K),in(A),in(B),in(C),st=(K+1)*n*n+1,ed=st+1;
	add_(st,P(1,1,0),1,0);
	for(Re k=1;k<=K;++k)add_(P(n,n,k),ed,1,0);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=n;++j){
			in(x);
			if(x){
				for(Re k=1;k<=K;++k)add_(P(i,j,k),P(i,j,0),inf,A);
				if(i<n)add_(P(i,j,0),P(i+1,j,1),inf,0);
				if(j<n)add_(P(i,j,0),P(i,j+1,1),inf,0);
				if(i>1)add_(P(i,j,0),P(i-1,j,1),inf,B);
				if(j>1)add_(P(i,j,0),P(i,j-1,1),inf,B);
			}
			else{
				for(Re k=0;k<K;++k){
					if(i<n)add_(P(i,j,k),P(i+1,j,k+1),inf,0);
					if(j<n)add_(P(i,j,k),P(i,j+1,k+1),inf,0);
					if(i>1)add_(P(i,j,k),P(i-1,j,k+1),inf,B);
					if(j>1)add_(P(i,j,k),P(i,j-1,k+1),inf,B);
				}
				add_(P(i,j,K),P(i,j,0),1,A+C);
			}
		}
	EK(st,ed);
	printf("%lld",mincost);
}
深海机器人问题 (EK) MCMF 3.3.5 网络流
57 行
CPP JSON
【深海机器人问题 (EK)(MCMF)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z,Re w) — 加法更新 void add_(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 int Poi(Re x,Re y) — 核心算法函数 核心结构体:QAQ 关键配置: N=260,M=1540,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 56 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=260,M=1540,inf=2e9;
int x,y,z,o=1,n,m,h,t,Q1,Q2,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow; 
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
	Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w,pre[to]=i;
				cyf[to]=min(cyf[x],a[i].flow);
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
	while(SPFA(st,ed)){
		Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
inline int Poi(Re x,Re y){return (x-1)*m+y;}
int main(){
	in(Q1),in(Q2),in(n),in(m),++n,++m,st=n*m+1,ed=st+1;
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<m;++j)
			in(x),add_(Poi(i,j),Poi(i,j+1),1,x),add_(Poi(i,j),Poi(i,j+1),inf,0);
	for(Re j=1;j<=m;++j)
		for(Re i=1;i<n;++i)
			in(x),add_(Poi(i,j),Poi(i+1,j),1,x),add_(Poi(i,j),Poi(i+1,j),inf,0);
	while(Q1--)in(z),in(x),in(y),add_(st,Poi(x+1,y+1),z,0);
	while(Q2--)in(z),in(x),in(y),add_(Poi(x+1,y+1),ed,z,0);
	EK(st,ed);
	printf("%lld",maxcost);
}
航空路线问题 (EK) MCMF 3.3.5 网络流
74 行
CPP JSON
【航空路线问题 (EK)(MCMF)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void add(Re x,Re y,Re z,Re w) — 加法更新 void add_(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 void dfs1(Re x) — 深度优先搜索遍历 void dfs2(Re x) — 深度优先搜索遍历 核心结构体:QAQ 关键配置: N=103,M=40000,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 73 行 CPP
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<queue>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=40000,inf=2e9;
int x,y,o=1,n,m,h,t,st,ed,flag,cyf[N],pan[N],pre[N],dis[N],head[N];LL maxcost,maxflow;
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;string CH,ch[N];map<string,int>ip;
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=ed;++i)dis[i]=-inf,pan[i]=0;
	Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&dis[to=a[i].to]<dis[x]+a[i].w){//�· 
				dis[to]=dis[x]+a[i].w,pre[to]=i;
				cyf[to]=min(cyf[x],a[i].flow);
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return dis[ed]!=-inf;
}
inline void EK(Re st,Re ed){
	while(SPFA(st,ed)){
		Re x=ed;maxflow+=cyf[ed],maxcost+=(LL)cyf[ed]*dis[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
inline void dfs1(Re x){
	pan[x]=1;
	cout<<ch[x-n]<<endl;
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)<=n&&!a[i].flow){dfs1(to+n);break;}
}
inline void dfs2(Re x){
	for(Re i=head[x],to;i;i=a[i].next)
		if((to=a[i].to)<=n&&!a[i].flow&&!pan[to+n])dfs2(to+n);
	cout<<ch[x-n]<<endl;
}
int main(){
	cin>>n>>m;st=1,ed=n<<1;
	for(Re i=1;i<=n;++i)cin>>ch[i],ip[ch[i]]=i;
	for(Re i=2;i<n;++i)add_(i,n+i,1,1);
	add_(1,1+n,2,1),add_(n,n+n,2,1);
	while(m--){
		cin>>CH;x=ip[CH];
		cin>>CH;y=ip[CH];
		if(x>y)swap(x,y);
		flag|=x==1&&y==n; 
		add_(x+n,y,1,0);
	}
	EK(st,ed);
	if(maxflow==2)printf("%d\n",maxcost-2);
	else if(maxflow==1&&flag){
		printf("2\n");
		cout<<ch[1]<<endl<<ch[n]<<endl<<ch[1]<<endl;
		return 0;
	}
	else return !printf("No Solution!\n");
	for(Re i=1;i<=n+2;++i)pan[i+n]=0;
	dfs1(1+n),dfs2(1+n);
}
负载平衡问题 (EK) MCMF 3.3.5 网络流
55 行
CPP JSON
【负载平衡问题 (EK)(MCMF)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z,Re w) — 加法更新 void add_(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=103,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 54 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=103,inf=2e9;
int o=1,n,h,t,S,st,ed,A[N],cyf[N],pan[N],pre[N],dis[N],head[N];LL mincost; 
struct QAQ{int w,to,next,flow;}a[N<<3];queue<int>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=n;++i)dis[i]=inf,pan[i]=0;
	Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w,pre[to]=i;
				cyf[to]=min(cyf[x],a[i].flow);
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
	while(SPFA(st,ed)){
		Re x=ed;mincost+=(LL)cyf[ed]*dis[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
int main(){
	in(n);st=n+1,ed=n+2;
	for(Re i=1;i<=n;++i)in(A[i]),S+=A[i];S/=n;
	for(Re i=1;i<=n;++i){
		if(i>1)add_(i,i-1,inf,1),add_(i-1,i,inf,1);
		if(A[i]>S)add_(st,i,A[i]-S,0);
		else if(A[i]<S)add_(i,ed,S-A[i],0);
	}
	add_(1,n,inf,1),add_(n,1,inf,1);
	n+=2;EK(st,ed);
	printf("%lld",mincost);
}
运输问题 (EK) MCMF 3.3.5 网络流
66 行
CPP JSON
【运输问题 (EK)(MCMF)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z,Re w) — 加法更新 void add_(Re a,Re b,Re flow,Re w) — 加法更新 int SPFA(Re st,Re ed) — SPFA最短路 void EK(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=205,M=10205,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 65 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=205,M=10205,inf=2e9;
int o=1,n,m,h,t,st,ed,cyf[N],pan[N],pre[N],dis[N],head[N],Flow[N][2],Cost[N][N];LL mincost,maxflow; 
struct QAQ{int w,to,next,flow;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z,Re w){a[++o].flow=z,a[o].w=w,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re a,Re b,Re flow,Re w){add(a,b,flow,w),add(b,a,0,-w);}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=ed;++i)dis[i]=inf,pan[i]=0;
	Q.push(st),pan[st]=1,dis[st]=0,cyf[st]=inf;
	while(!Q.empty()){
		Re x=Q.front();Q.pop();pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w,pre[to]=i;
				cyf[to]=min(cyf[x],a[i].flow);
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return dis[ed]!=inf;
}
inline void EK(Re st,Re ed){
	while(SPFA(st,ed)){
		Re x=ed;maxflow+=cyf[ed],mincost+=(LL)cyf[ed]*dis[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
int main(){
	in(n),in(m),st=n+m+1,ed=st+1;
	for(Re i=1;i<=n;++i)in(Flow[i][0]),add_(st,i,Flow[i][0],0);
	for(Re i=1;i<=m;++i)in(Flow[i][1]),add_(n+i,ed,Flow[i][1],0);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(Cost[i][j]),add_(i,n+j,inf,Cost[i][j]);
	EK(st,ed);
	printf("%lld\n",mincost);
	memset(head,0,sizeof(head));
	memset(cyf,0,sizeof(cyf));
	memset(pre,0,sizeof(pre));
	memset(a,0,sizeof(a));
	o=1;maxflow=mincost=0;
	for(Re i=1;i<=n;++i)add_(st,i,Flow[i][0],0);
	for(Re i=1;i<=m;++i)add_(n+i,ed,Flow[i][1],0);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			add_(i,n+j,inf,-Cost[i][j]);
	EK(st,ed);
	printf("%lld\n",-mincost);
}
飞行员配对方案问题 Dinic 3.3.5 网络流
57 行
CPP JSON
【飞行员配对方案问题(Dinic)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void Dinic(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=103,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 56 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=2e9;
int x,y,n,m,o=1,h,t,st,ed,ans,maxflow,Q[N],dis[N],head[N];
struct QAQ{int to,next,flow;}a[N*N*2+N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){
	for(Re i=0;i<=n+2;++i)dis[i]=0;
	h=1,t=0,dis[st]=1,Q[++t]=st;
	while(h<=t){
		Re to,x=Q[h++];
		for(Re i=head[x];i;i=a[i].next)
			if(a[i].flow&&!dis[to=a[i].to]){
				dis[to]=dis[x]+1,Q[++t]=to;
				if(to==ed)return 1;
			}
	}
	return 0;
}
inline int dfs(Re x,Re flow){
	if(!flow||x==ed)return flow;
	Re tmp=0,to,f;
	for(Re i=head[x];i;i=a[i].next)
		if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
			a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
			if(flow==tmp)break;
		}
	return tmp;
}
inline void Dinic(Re st,Re ed){
	Re flow=0;while(bfs(st,ed))while(flow=dfs(st,inf))maxflow+=flow;
}
int main(){
	in(m),in(n),st=n+1,ed=n+2;
	while(1){
		in(x),in(y);
		if(x==-1)break;
		add(x,y,1),add(y,x,0);
	}
	for(Re i=1;i<=m;++i)add(st,i,1),add(i,st,0);
	for(Re i=m+1;i<=n;++i)add(i,ed,1),add(ed,i,0);
	Dinic(st,ed);
	printf("%d\n",maxflow);
	for(Re x=1;x<=m;++x)
		for(Re i=head[x];i;i=a[i].next)
			if(!(i&1)&&a[i].to!=st&&!a[i].flow)printf("%d %d\n",x,a[i].to);
}
飞行员配对方案问题 EK 3.3.5 网络流
57 行
CPP JSON
【飞行员配对方案问题(EK)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 void EK(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=103,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 56 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=2e9;
int x,y,n,m,o=1,h,t,st,ed,ans,maxflow,cyf[N],Q[N],pre[N],pan[N],head[N];
struct QAQ{int to,next,flow;}a[N*N*2+N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline int bfs(Re st,Re ed){
	for(Re i=0;i<=n+2;++i)pan[i]=0;
	h=1,t=0,pan[st]=1,cyf[st]=inf,Q[++t]=st;
	while(h<=t){
		Re to,x=Q[h++];
		for(Re i=head[x];i;i=a[i].next)
			if(a[i].flow&&!pan[to=a[i].to]){
				cyf[to]=min(cyf[x],a[i].flow);
				pan[to]=1,pre[to]=i,Q[++t]=to;
				if(to==ed)return 1;
			}
	}
	return 0;
}
inline void EK(Re st,Re ed){
	while(bfs(st,ed)){
		maxflow+=cyf[ed];
		Re x=ed;
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
int main(){
	in(m),in(n),st=n+1,ed=n+2;
	while(1){
		in(x),in(y);
		if(x==-1)break;
		add(x,y,1),add(y,x,0);
	}
	for(Re i=1;i<=m;++i)add(st,i,1),add(i,st,0);
	for(Re i=m+1;i<=n;++i)add(i,ed,1),add(ed,i,0);
	EK(st,ed);
	printf("%d\n",maxflow);
	for(Re x=1;x<=m;++x)
		for(Re i=head[x];i;i=a[i].next)
			if(!(i&1)&&a[i].to!=st&&!a[i].flow)printf("%d %d\n",x,a[i].to);
}
魔术球问题 Dinic 3.3.5 网络流
63 行
CPP JSON
【魔术球问题(Dinic)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void add(Re x,Re y,Re flow) — 加法更新 void add_(Re x,Re y,Re flow) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void Dinic(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=1e5+5,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 说明:freopen("123.txt","r",stdin); 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 62 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define Re register int
using namespace std;
const int N=1e5+5,inf=2e9;
int h,t,n,p,o=1,st,ed,cnt,maxflow,Q[N],zhu[N],ans[N],pan[N],pre[N],dis[N],head[N];
struct QAQ{int to,flow,next;}a[N<<1];vector<int>Ans[N];
inline void add(Re x,Re y,Re flow){a[++o].flow=flow,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re flow){add(x,y,flow),add(y,x,0);}
inline int bfs(Re st,Re ed){
	for(Re i=0;i<=ed;++i)dis[i]=0;
	h=1,t=0,dis[st]=1,Q[++t]=st;
	while(h<=t){
		Re x=Q[h++],to;
		for(Re i=head[x];i;i=a[i].next)
			if(a[i].flow&&!dis[to=a[i].to]){
				dis[to]=dis[x]+1,Q[++t]=to;
				if(to==ed)return 1;
			}
	}
	return 0;
}
inline int dfs(Re x,Re flow){
	if(!flow||x==ed)return flow;
	Re tmp=0,to,f;
	for(Re i=head[x];i;i=a[i].next)
		if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
			a[i].flow-=f,a[i^1].flow+=f;
			tmp+=f,pre[to]=i;
			if(!(flow-tmp))break;
		}
	return tmp;
}
inline void Dinic(Re st,Re ed){
	Re flow=0;maxflow=0;
	while(bfs(st,ed))while(flow=dfs(st,inf))maxflow+=flow;
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%d",&n),st=1e5+1,ed=st+1;
	while(ans[0]<=n){
		++p;
		add_(st,p<<1,1),add_(p<<1|1,ed,1);
		for(Re j=sqrt(p)+1;j*j-p<=p-1;++j)add_((j*j-p)<<1,(p<<1)|1,1);
		Dinic(st,ed);
		if(!maxflow)ans[++ans[0]]=p,Ans[zhu[p]=ans[0]].push_back(p);
		else{
			Re x=p<<1|1;
			while(!zhu[x-1>>1])x=a[pre[x]^1].to+1;
			Ans[zhu[x-1>>1]].push_back(p);
		}
	}
	printf("%d\n",p-1);
	for(Re i=1;i<=n;puts(""),++i)
		for(Re j=0;j<Ans[i].size();++j)
			printf("%d ",Ans[i][j]);
}
魔术球问题 EK 3.3.5 网络流
61 行
CPP JSON
【魔术球问题(EK)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void add(Re x,Re y,Re flow) — 加法更新 void add_(Re x,Re y,Re flow) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 void EK(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=1e5+5,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 说明:freopen("123.txt","r",stdin); 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 60 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define Re register int
using namespace std;
const int N=1e5+5,inf=2e9;
int h,t,n,p,o=1,st,ed,cnt,maxflow,Q[N],zhu[N],ans[N],pan[N],pre[N],cyf[N],head[N];
struct QAQ{int to,flow,next;}a[N<<1];vector<int>Ans[N];
inline void add(Re x,Re y,Re flow){a[++o].flow=flow,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re flow){add(x,y,flow),add(y,x,0);}
inline int bfs(Re st,Re ed){
	for(Re i=1;i<=ed;++i)pan[i]=0;
	h=1,t=0,pan[st]=1,Q[++t]=st,cyf[st]=inf;
	while(h<=t){
		Re x=Q[h++];
		for(Re i=head[x],to;i;i=a[i].next)
			if(a[i].flow&&!pan[to=a[i].to]){
				cyf[to]=min(cyf[x],a[i].flow);
				pan[Q[++t]=to]=1,pre[to]=i;
				if(to==ed)return 1;
			}
	}
	return 0;
}
inline void EK(Re st,Re ed){
	Re x,flow=0;maxflow=0;
	while(bfs(st,ed)){
		x=ed,maxflow+=cyf[ed];
		while(x!=st){
			Re i=pre[x];
			a[i].flow-=cyf[ed];
			a[i^1].flow+=cyf[ed];
			x=a[i^1].to;
		}
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%d",&n),st=1e5+1,ed=st+1;
	while(ans[0]<=n){
		++p;
		add_(st,p<<1,1),add_(p<<1|1,ed,1);
		for(Re j=sqrt(p)+1;j*j-p<=p-1;++j)add_((j*j-p)<<1,(p<<1)|1,1);
		EK(st,ed);
		if(!maxflow)ans[++ans[0]]=p,Ans[zhu[p]=ans[0]].push_back(p);
		else{
			Re x=p<<1|1;
			while(!zhu[x-1>>1])x=a[pre[x]^1].to+1;
			Ans[zhu[x-1>>1]].push_back(p);
		}
	}
	printf("%d\n",p-1);
	for(Re i=1;i<=n;puts(""),++i)
		for(Re j=0;j<Ans[i].size();++j)
			printf("%d ",Ans[i][j]);
}
教辅的组成 Dinic 3.3.5 网络流
56 行
CPP JSON
【教辅的组成(Dinic)】 最大流(Dinic)模板,含当前弧优化与多路增广。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void add_(Re x,Re y,Re flow) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void Dinic(Re st,Re ed) — 核心算法函数 核心结构体:QAQ 关键配置: N=4e4+5,M=7e4+3,inf=2e9 复杂度:一般图 O(V²E),二分图 O(E√V) 适用场景:最大流/最小割建模、二分图匹配、任务分配问题
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=4e4+5,M=7e4+3,inf=2e9;
int x,y,z,o=1,n1,n2,n3,nn,m,h,t,st,ed,Q[N],dis[N],pan[N],pre[N],head[N];long long maxflow; 
struct QAQ{int to,next,flow;}a[M<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].flow=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void add_(Re x,Re y,Re flow){add(x,y,flow),add(y,x,0);}
inline int bfs(Re st,Re ed){
	for(Re i=0;i<=ed;++i)dis[i]=0;
	h=1,t=0,dis[st]=1,Q[++t]=st;
	while(h<=t){
		Re x=Q[h++],to;
		for(Re i=head[x];i;i=a[i].next)
			if(a[i].flow&&!dis[to=a[i].to]){
				dis[to]=dis[x]+1,Q[++t]=to;
				if(to==ed)return 1;
			}
	}
	return 0;
}
inline int dfs(Re x,Re flow){
	if(!flow||x==ed)return flow;
	Re tmp=0,to,f;
	for(Re i=head[x];i;i=a[i].next)
		if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(flow-tmp,a[i].flow)))){
			a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
			if(!(flow-tmp))break;
		}
	return tmp;
}
inline void Dinic(Re st,Re ed){
	Re flow=0;
	while(bfs(st,ed))while(flow=dfs(st,inf))maxflow+=flow;
}
int main(){
	freopen("123.txt","r",stdin);
	in(n1),in(n2),in(n3);nn=n1+n2+n3,st=nn+n1+1,ed=st+1;
	for(Re i=1;i<=n1;++i)add_(i,i+nn,1);
	for(Re i=1;i<=n2;++i)add_(st,n1+i,1);
	for(Re i=1;i<=n3;++i)add_(n1+n2+i,ed,1);
	in(m);while(m--)in(x),in(y),add_(n1+y,x,1);
	in(m);while(m--)in(x),in(y),add_(x+nn,n1+n2+y,1);
	Dinic(st,ed);
	printf("%lld",maxflow);
}
01分数规划 观光奶牛Sightseeing Cows 3.3.6 负环与差分约束
43 行
CPP JSON
【01分数规划(观光奶牛Sightseeing Cows)】 负环检测与差分约束系统模板,基于 SPFA/Bellman-Ford。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 int SPFA(Re st,double mid) — SPFA最短路 核心结构体:QAQ 关键配置: N=1e4+5,M=5e5+5,inf=2e9
C++ 42 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=5e5+5,inf=2e9;
int x,y,z,n,m,o,T,to,A[N],cha[N],pan[N],head[N];double dis[N];
struct QAQ{int w,to,next;}a[M<<1];queue<int>Q;
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline int SPFA(Re st,double mid){
    for(Re i=0;i<=n;++i)dis[i]=-inf,pan[i]=cha[i]=0;
    dis[st]=0,cha[st]=pan[st]=1,Q.push(st);
    while(!Q.empty()){
        x=Q.front(),Q.pop();
        pan[x]=0;
        for(Re i=head[x];i;i=a[i].next)
            if(dis[to=a[i].to]<dis[x]+A[x]-mid*a[i].w){
                dis[to]=dis[x]+A[x]-mid*a[i].w;
                if(++cha[to]>n)return 1;
                if(!pan[to])Q.push(to);
            }
    }
    return 0;
}
int main(){
    in(n),in(m);
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),in(z),add(x,y,z);
    double l=0,r=1000000,mid;
    while(r-l>1e-4){
        mid=(l+r)/2;
        if(SPFA(1,mid))l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
}
42 行
CPP JSON
【判负环(SPFA)】 负环检测与差分约束系统模板,基于 SPFA/Bellman-Ford。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 int SPFA(Re st) — SPFA最短路 核心结构体:QAQ 关键配置: N=2003,M=3e5+3,inf=2e9 说明:if(++chu[to]>=n)return 1;
C++ 41 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=2003,M=3e5+3,inf=2e9;
int n,m,x,y,z,o,T,pan[N],chu[N],dis[N],head[N];queue<int>Q;
struct QAQ{int w,to,next;}a[M<<1];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int SPFA(Re st){
    for(Re i=1;i<=n;++i)dis[i]=inf,chu[i]=pan[i]=0;
    while(!Q.empty())Q.pop();
    Q.push(st),dis[st]=0,chu[st]=0,pan[st]=1;
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to;i;i=a[i].next)
            if(dis[to=a[i].to]>dis[x]+a[i].w){
                dis[to]=dis[x]+a[i].w;
                if((chu[to]=chu[x]+1)>=n)return 1;
//                if(++chu[to]>=n)return 1;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
    }
    return 0;
}
int main(){
    in(T);
    while(T--){
        in(n),in(m),memset(head,0,sizeof(head)),o=0;
        while(m--){in(x),in(y),in(z),add(x,y,z);if(z>=0)add(y,x,z);}
        puts(SPFA(1)?"YES":"NO");
    }
}
差分约束系统 糖果 3.3.6 负环与差分约束
49 行
CPP JSON
【差分约束系统(糖果)】 负环检测与差分约束系统模板,基于 SPFA/Bellman-Ford。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 int SPFA(Re st,Re ed) — SPFA最短路 核心结构体:QAQ 关键配置: N=1e5+5,M=3e5+5,inf=2e9
C++ 48 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=3e5+5,inf=2e9;
int x,y,n,m,o,op,chu[N],dis[N],pan[N],head[N];long long ans;
struct QAQ{int w,to,next;}a[M];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline int SPFA(Re st,Re ed){
	for(Re i=0;i<=n;++i)dis[i]=-inf,chu[i]=0;
	dis[st]=0,chu[st]=pan[st]=1,Q.push(st);
	while(!Q.empty()){
		x=Q.front(),Q.pop();
		pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(dis[to=a[i].to]<dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w;
				if((chu[to]=chu[x]+1)>n+1)return 1;
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
	return 0;
}
int main(){
	in(n),in(m);
	for(Re i=n;i>=1;--i)add(0,i,1); //a[i]>=a[0]=1,a[i]-a[0]>=1
	while(m--){
		in(op),in(x),in(y);
		if(op<2)add(y,x,0),add(x,y,0);
		else if(op<3)add(x,y,1);//a[x]<a[y]: a[y]-a[x]>=1
		else if(op<4)add(y,x,0);//a[x]>=a[y]: a[x]-a[y]>=0
		else if(op<5)add(y,x,1);//a[x]>a[y]: a[x]-a[y]>=1
		else add(x,y,0);//a[x]<=a[y]: a[y]-a[x]>=0
		if(!(op%2)&&x==y){puts("-1");return 0;}
	}
	if(SPFA(0,n))puts("-1");
	else{
		for(Re i=1;i<=n;++i)ans+=dis[i];
		printf("%lld",ans);
	}
}
线段树优化建边+Dijkstra最短路 Legacy 3.3.7 线段树优化建图
69 行
CPP JSON
【线段树优化建边+Dijkstra最短路(Legacy)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w,Re op) — 核心算法函数 void dijkstra(Re st) — Dijkstra最短路 核心结构体:QAQ, Segment_Tree, QAQ, QWQ 关键配置: N=1e5+3 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 68 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,x,y,w,l,r,o,op,st,head[N<<3];bool pan[N<<3];LL dis[N<<3];
struct QAQ{int w,to,next;}a[(N<<3)+(N<<2)+N*18*2];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int in,out;}tr[N<<2];
	inline void build(Re p,Re L,Re R){
		if(L==R){tr[p].in=tr[p].out=L;return;}
		tr[p].in=++O,tr[p].out=++O,add(tr[p].in,tr[p].out,0);
		build(pl,L,mid),build(pr,mid+1,R);
		add(tr[p].in,tr[pl].in,0),add(tr[p].in,tr[pr].in,0);
		add(tr[pl].out,tr[p].out,0),add(tr[pr].out,tr[p].out,0);
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w,Re op){
		if(l<=L&&R<=r){
			if(op)add(tr[p].out,x,w);
			else add(x,tr[p].in,w);
			return;
		}
		if(l<=mid)change(pl,L,mid,l,r,x,w,op);
		if(r>mid)change(pr,mid+1,R,l,r,x,w,op);
	}
}TR;
struct QWQ{int x;LL d;inline bool operator<(const QWQ &O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void dijkstra(Re st){
	for(Re i=1;i<=TR.O;++i)dis[i]=inf;
	Q.push((QWQ){st,dis[st]=0});
	while(!Q.empty()){
		Re x=Q.top().x;Q.pop();
		if(pan[x])continue;
		pan[x]=0;
		for(Re i=head[x],to;i;i=a[i].next)
			if(dis[to=a[i].to]>dis[x]+a[i].w)
				Q.push((QWQ){to,dis[to]=dis[x]+a[i].w});
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(st);
	TR.O=n,TR.build(1,1,n);
	while(m--){
		in(op),in(x);
		if(op<2)in(y),in(w),TR.change(1,1,n,y,y,x,w,0);
		else if(op<3)in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,0);
		else in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,1);
	}
	dijkstra(st);
	for(Re i=1;i<=n;++i)printf("%lld ",dis[i]==inf?-1:dis[i]);
}
线段树优化建边+Dinic最大流 Last chance 3.3.7 线段树优化建图
100 行
CPP JSON
【线段树优化建边+Dinic最大流(Last chance)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void in(Re &x) — 核心算法函数 void add_(Re x,Re y,Re flow) — 加法更新 void add(Re x,Re y,Re flow) — 加法更新 int bfs(Re st,Re ed) — 广度优先搜索遍历 int dfs(Re x,Re flow) — 深度优先搜索遍历 void dinic(Re st,Re ed) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) 核心结构体:Network_Flow, QAQ, Segment_Tree, QAQ 关键配置: N=5003+3,M=25e4+3,inf=2e9 复杂度:建树 O(N),单次操作 O(log N) 说明:freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 99 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5003+3,M=25e4+3,inf=2e9;
int n,m,x,y,z,O,op,st,ed,X[N],Y[N],Z[N],Ans[N],cnt[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Network_Flow{
	int o,h,t,maxflow,Q[N*3],dis[N*3],cur[N*3],head[N*3];
	struct QAQ{int to,next,flow;}a[M<<1];
	inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
	inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
	inline int bfs(Re st,Re ed){
		for(Re i=0;i<=ed;++i)dis[i]=0,cur[i]=head[i];
		h=1,t=0,dis[Q[++t]=st]=1;
		while(h<=t){
			Re x=Q[h++];
			for(Re i=head[x],to;i;i=a[i].next)
				if(a[i].flow&&!dis[to=a[i].to]){
					dis[Q[++t]=to]=dis[x]+1;
					if(to==ed)return 1;
				}
		}
		return 0;
	}
	inline int dfs(Re x,Re flow){
		if(x==ed||!flow)return flow;
		Re tmp=0,to,f;
		for(Re i=cur[x];i;i=a[i].next){
			cur[x]=i;
			if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(a[i].flow,flow-tmp)))){
				a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
				if(tmp==flow)break;
			}
		}
		return tmp;
	}
	inline void dinic(Re st,Re ed){while(bfs(st,ed))maxflow+=dfs(st,inf);}
	inline int find(Re x){
		Re last=ed;
		while(x<=O||x>O+n){
			for(Re i=head[x];i;i=a[i].next)
				if(a[i^1].to==x&&a[i].to!=last&&a[i].flow){
					--a[i].flow,last=x,x=a[i].to;break;
				}
		}
		return x-O;
	}
}T1;
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	struct QAQ{int in;}tr[N<<2];
	inline void build(Re p,Re L,Re R){
		if(L==R){tr[p].in=L;return;}
		tr[p].in=++O,build(pl,L,mid),build(pr,mid+1,R);
		T1.add(tr[p].in,tr[pl].in,inf),T1.add(tr[p].in,tr[pr].in,inf);
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w){
		if(l<=L&&R<=r){T1.add(x,tr[p].in,w);return;}
		if(l<=mid)change(pl,L,mid,l,r,x,w);
		if(r>mid)change(pr,mid+1,R,l,r,x,w);
	}
}TR;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),T1.o=1,O=m,TR.build(1,1,m),st=O+n+1,ed=st+1;
	for(Re i=1;i<=n;++i){
		in(op);
		if(op<1){
			in(x),T1.add(st,O+i,1);
			while(x--)in(y),T1.add(O+i,y,1);
		}
		else if(op<2)in(x),in(y),T1.add(st,O+i,1),TR.change(1,1,m,x,y,O+i,1);
		else{
			in(x),in(y),in(z),T1.add(st,O+i,2),X[i]=x,Y[i]=y,Z[i]=z;
			T1.add(O+i,x,1),T1.add(O+i,y,1),T1.add(O+i,z,1);
		}
	}
	for(Re j=1;j<=m;++j)T1.add(j,ed,1);
	T1.dinic(st,ed),printf("%d\n",T1.maxflow);
	for(Re i=T1.head[ed];i;i=T1.a[i].next)
		if(T1.a[i].flow)++cnt[Ans[T1.a[i].to]=T1.find(T1.a[i].to)];
	for(Re i=1;i<=n;++i)
		if(X[i]&&cnt[i]==1){
			if(Ans[X[i]]==i)Ans[Y[i]]=i;
			else Ans[X[i]]=i;
		}
	for(Re i=1;i<=m;++i)if(Ans[i])printf("%d %d\n",Ans[i],i);
}
线段树优化建边+Tarjan缩点 炸弹 3.3.7 线段树优化建图
103 行
CPP JSON
【线段树优化建边+Tarjan缩点(炸弹)】 线段树(Segment Tree)模板,支持区间操作的高效数据结构。 核心函数: void add(Re x,Re y) — 加法更新 template<typename T>inline void in(T &x) — 核心算法函数 void build(Re p,Re L,Re R) — 构建数据结构(建树/建图) void change(Re p,Re L,Re R,Re l,Re r,Re x) — 核心算法函数 int find1(LL x,Re r) — 查找(并查集寻根/二分查找) int find2(LL x,Re l) — 查找(并查集寻根/二分查找) void add(Re x,Re y) — 加法更新 void dfs(Re x) — 深度优先搜索遍历 核心结构体:QAQ, Segment_Tree, QAQ, Tuopu, QAQ 关键配置: N=5e5+3,M=(N<<2)+N*18*2,P=1e9+7 复杂度:建树 O(N),单次操作 O(log N) 说明:printf("(x=%d) -> (l=%d,r=%d) w=%d\n",x,l,r,w);return;;freopen("123.txt","r",stdin); 适用场景:区间最值/和查询、区间加/乘/赋值修改、区间合并统计等
C++ 102 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=5e5+3,M=(N<<2)+N*18*2,P=1e9+7;
int o,n,Ans,head[N<<2];LL X[N],R[N];
struct QAQ{int x,to,next;}a[M];map<pair<int,int>,int>vis;
inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
template<typename T>inline void in(T &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Segment_Tree{
	#define pl (p<<1)
	#define pr (p<<1|1)
	#define mid ((L+R)>>1)
	int O;
	struct QAQ{int in;}tr[N<<2];
	inline void build(Re p,Re L,Re R){
		if(L==R){tr[p].in=L;return;}
		tr[p].in=++O;
		build(pl,L,mid),build(pr,mid+1,R);
		add(tr[p].in,tr[pl].in),add(tr[p].in,tr[pr].in);
	}
	inline void change(Re p,Re L,Re R,Re l,Re r,Re x){
//		printf("(x=%d) -> (l=%d,r=%d) w=%d\n",x,l,r,w);return;
		if(l<=L&&R<=r){add(x,tr[p].in);return;}
		if(l<=mid)change(pl,L,mid,l,r,x);
		if(r>mid)change(pr,mid+1,R,l,r,x);
	}
}TR;
inline int find1(LL x,Re r){
	Re l=1;
	while(l<r){
		Re Mid=l+r>>1;
		if(X[Mid]<x)l=Mid+1;
		else r=Mid;
	}
	return r;
}
inline int find2(LL x,Re l){
	Re r=n;
	while(l<r){
		Re Mid=l+r+1>>1;
		if(X[Mid]>x)r=Mid-1;
		else l=Mid;
	}
	return l;
}
struct Tuopu{
	int o,n,L[N<<2],R[N<<2],ru[N<<2],pan[N<<2],head[N<<2];queue<int>Q;
	struct QAQ{int to,next;}a[M];
	inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
	inline void dfs(Re x){
		if(pan[x])return;
		pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			dfs(to=a[i].to),L[x]=min(L[x],L[to]),R[x]=max(R[x],R[to]);
	}
	inline void sakura(){for(Re i=1;i<=n;++i)if(!ru[i])dfs(i);}
}T2;
int Q_o,ip[N<<2];
struct Tarjan{
	int n,t,dfn_o,Q[N<<2],low[N<<2],dfn[N<<2],pan[N<<2];
	inline void tarjan(Re x){
		dfn[x]=low[x]=++dfn_o,Q[++t]=x,pan[x]=1;
		for(Re i=head[x],to;i;i=a[i].next)
			if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
			else if(pan[to])low[x]=min(low[x],dfn[to]);
		if(low[x]==dfn[x]){
			++Q_o,T2.L[Q_o]=n+1,T2.R[Q_o]=-1;
			while(1){
				ip[Q[t]]=Q_o,pan[Q[t]]=0;
				if(x==Q[t--])break;
			}
		}
	}
	inline void sakura(){
		for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);
		for(Re i=1,x,y;i<=o;++i)
			if((x=ip[a[i].x])!=(y=ip[a[i].to])&&!vis[mp(x,y)])
				vis[mp(x,y)]=1,++T2.ru[y],T2.add(x,y);
	}
}T1;
int main(){
//	freopen("123.txt","r",stdin);
	in(n),TR.O=n,TR.build(1,1,n);
	for(Re i=1;i<=n;++i)in(X[i]),in(R[i]);
	for(Re i=1;i<=n;++i)TR.change(1,1,n,find1(X[i]-R[i],i),find2(X[i]+R[i],i),i);
	T1.n=TR.O,T1.sakura();
	for(Re i=1;i<=n;++i)T2.L[ip[i]]=min(T2.L[ip[i]],i),T2.R[ip[i]]=max(T2.R[ip[i]],i);;
	T2.n=Q_o,T2.sakura();
	for(Re i=1;i<=n;++i)(Ans+=(LL)i*(T2.R[ip[i]]-T2.L[ip[i]]+1)%P)%=P;
	printf("%d\n",Ans);
}
已复制