模板整理--图论(持续更新)

图论 ACM模板
ACM
发布日期:   2020-12-13
文章字数:   2.2k
阅读时长:   11 分
阅读次数:  

网络流相关

SFPA

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
const int MAXN = 114514;
const int MAXM = 514514;
const ll LINF = 1ll<<61;
//前向星
struct Edge{
    int to,w,nxt;
}edges[MAXM];
int head[MAXN];
int n,m,s;
int cnt;
inline void add_edge(int u,int v,int w){
    edges[cnt].to = v;
    edges[cnt].w = w;
    edges[cnt].nxt = head[u];
    head[u] = cnt++;
}
//SPFA
queue<int> q;
ll dis[MAXN];//每个点当前最小距离
bool vis[MAXN];//记录队列中是否有该点
inline void init(){//初始化前向星和SPFA的dis数组
    rep(i,1,n) dis[i]=LINF,head[i]=-1;
    cnt = 0;
}
inline void solve(){
    cin>>n>>m>>s;
    init();//记得要初始化
    int u,v,w;
    rep(i,1,m){
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    dis[s] = 0;
    q.push(s);
    int now;
    while(!q.empty()){
        now = q.front();
        q.pop();
        vis[now] = 0;//vis表示队中有无该点
        //每次取出队首,并检查关联点是否可以进行松弛操作
        for(int i=head[now];i!=-1;i=edges[i].nxt){
            v = edges[i].to;
            if(dis[v]>dis[now]+edges[i].w){//松弛操作
                dis[v] = dis[now]+edges[i].w;
                if(!vis[v]){//如果队列中没有点v,则将v入队
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    rep(i,1,n) cout<<dis[i]<<' ';
    //我这里还没有对到达不了的特殊情况进行处理
    cout<<endl;
}
int main(){
    solve();
}

费用流-SPFA找最短增广路

#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define INF 0x7fffffff
const int N = 5e3+5;
const int M = 114514;//因为是双向边,要记得开两倍大的数组!
int n;
//前向星存图
int t=1;//总边数
int u[M],v[M],c[M],co[M],nxt[M],head[M];
inline void add_edge(int x,int y,int z,int zo){//起点终点流量费用
    u[++t]=x;v[t]=y;//正向边
    c[t]=z;co[t]=zo;
    nxt[t]=head[x];head[x]=t;
    u[++t]=y;v[t]=x;//反向边
    c[t]=0;co[t]=-zo;
    nxt[t]=head[y];head[y]=t;
}
//SPFA
int S,T;
int q[M],l,r;//双端队列
int dis[N];
bool in[N];//在不在queue中
int f[N];//记录路径
inline bool spfa(){
    rep(i,1,n) in[i]=0,dis[i]=INF;//初始化
    dis[S]=0;in[S]=1;
    l=r=M>>1;q[l]=S;//手写队列
    while(l<=r){
        int now=q[l++];//取队首
        if(now==T) continue;
        for(int i=head[now];i;i=nxt[i])
            if(c[i]&&dis[now]+co[i]<dis[v[i]]){//费用更小的路
                dis[v[i]]=dis[now]+co[i];
                f[v[i]]=i;//记录路径!增广路经过哪些边
                if(!in[v[i]]){//如果队中没有则入队
                    in[v[i]]=1;
                    if(dis[v[i]]<dis[q[l]])q[--l]=v[i];else q[++r]=v[i];
                    //双端队列优化spfa
                }
            }
        in[now]=0;
    }
    return dis[T]<INF;//是否找到增广路
}
int i,tmp;
inline void costflow(){
    int ans=0,flow=0;//最小费用,最大流
    while(spfa()){
        //从终点根据记录的f找到增广路
        for(tmp=INF,i=T;i!=S;i=u[f[i]]) if(tmp>c[f[i]]) tmp=c[f[i]];
        //求这一次流多少(所有边剩余流量中最小值)
        for(ans+=dis[i=T]*tmp;i!=S;i=u[f[i]]) c[f[i]]-=tmp,c[f[i]^1]+=tmp;
        //减去流量并加在反向边上,并且计算费用
        flow+=tmp;
    }
    printf("%d %d\n",flow,ans);
}
int main(){
    int m;
    scanf("%d%d%d%d",&n,&m,&S,&T);
    int u,v,z,zo;
    while(m--){
        scanf("%d%d%d%d",&u,&v,&z,&zo);
        add_edge(u,v,z,zo);
    }
    costflow();
}
//参考claris费用流板子
//洛谷P3381
//https://www.luogu.com.cn/problem/P3381

连通性相关

Tarjan求强连通分量

可以用于有向图问题的缩点。

$dfn[u]$记录当前节点u是第几个访问到的；

$low[u]$定义为$Subtree(u)$中$dfn(u)$最小的，或者$Subtree(u)$中的点通过**非树边(不在子树上的边)**（返祖边或者比$rt$还高的边？）$low[u]$初始值定u，如果通过边连到$rt$之上的点可更新，又递归通过儿子$low[v]$来更新。

连通图中有且仅有一个$dfn[u]=low[u]$,这个点是根节点。通过一个栈按照dfs的顺序入栈，回溯的时候判断如果一个点的$dfn[u]=low[u]$，则从这个点到栈顶的所有节点归入一个强连通分量。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
using namespace std;

template<class T>inline void read(T &x){x=0;char o,f=1;while(o=getchar(),o<48)if(o==45)f=-f;do x=(x<<3)+(x<<1)+(o^48);while(o=getchar(),o>47);x*=f;}
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=b;i--)
#define INF 0x3f3f3f3f
#define cendl printf("\n")
ll gcd(ll a,ll b){ while(b^=a^=b^=a%=b); return a; }
//#define INF 0x7fffffff

const int MAXN = 2e6+5;

int n;
vector<int> e[MAXN];//存图 
int dfn[MAXN],low[MAXN];
int dfncnt;//dfn自增下标 
int s[MAXN],tp;//数组模拟栈,tp记录大小 
bool in[MAXN];//记录该点是否在栈中 
int scc[MAXN],sc;//节点i所在scc的编号,sc记录有几个强连通 
int sz[MAXN];//强连通i的大小 
int indg[MAXN];//记录缩点后的入度（这题才有的 

void tarjan(int u){
	low[u]=dfn[u]=++dfncnt;//low初始值为自身dfn
	s[++tp]=u;//推u入栈，从1开始 
	in[u]=1;//记录u点在栈中 
	for(auto v:e[u]){//访问到新点的情况 
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);//用low[v}更新low[u] 
		}
		else if(in[v])//v被访问过，但是在栈中 
			low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){//u是连通分量的根节点
		sc++;//强连通数量++
		sz[sc] = 0; 
		while(s[tp]!=u){//u和u之后的点全部出栈 
			scc[s[tp]] = sc;//这个点包含于第几个强连通
			sz[sc]++;//u为根的这个强连通的大小 
			in[s[tp]] = 0;//出栈 
			tp--; 
		}
		scc[u] = sc;//给根节点标，属于第sc个强连通 
		sz[sc]++;
		in[u] = 0;
		tp--;
	}
} 

void reset(){
	tp = sc = dfncnt =0;
	rep(i,1,n){
		in[i] = dfn[i] = 0;//low不用清空，sz在之后用到再清空 
		e[i].clear();
	}
}

int main(){
	cin>>n;
	reset();
	int v;
	rep(u,1,n){
		while(cin>>v&&v!=0) e[u].push_back(v);
	} 
	rep(u,1,n)
		if(!dfn[u]) tarjan(u);
	rep(i,1,sc) indg[i] = 0;//这个不包含在tarjan里面，是这题记录入度的 
	rep(u,1,n){
		for(auto v:e[u]){
			if(scc[u]!=scc[v]) indg[scc[v]]++;
		}
	}
	int res = 0;
	rep(i,1,sc){
		if(indg[i]==0) res++;
	}
	cout<<res<<endl;
}
//洛谷P2835 刻录光盘 https://www.luogu.com.cn/problem/P2835#submit

Tarjan求割点

定义：去掉这个点，连通分量数量+1

无向图的$low[u]$在这里表述成：点$u$在不经过其父亲的情况下能达到的最小时间戳/过一条非树边达到的最小时间戳(最小的$dfn$)

对于某个顶点$u$，如果$u$的儿子$v$中，存在至少一个$low[v]\ge dfn[u]$，即v子树中无法回到祖先（即最高也只能回到父亲u），则u是割点。

如果是$dfn[u]=1$即祖先的点，满足儿子数量$\ge 2$即可。

#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int MAXN = 114514;
int n,m;
vector<int>e[MAXN];
bool vis[MAXN];
bool flag[MAXN];//标记割点
int res;//记录割点数量
int low[MAXN],dfn[MAXN],dfncnt;//老tarjan了

void Tarjan(int u,int pre){//pre=-1时代表是祖先
    vis[u] = 1;
    low[u] = dfn[u] = ++dfncnt;
    int cntchild=0;//儿子数量
    for(auto v:e[u]){
        if(!vis[v]){
            cntchild++;
            Tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(pre!=-1&&low[v]>=dfn[u]&&!flag[u]){//算法核心
                flag[u]=1;
                res++;
            }
        }
        else if(v!=pre)//往上的边,更新当前节点的low
            low[u] = min(low[u],dfn[v]);
    }
    if(pre==-1&&cntchild>=2&&!flag[u]){//u为祖先要另外讨论
        flag[u]=1;
        res++;
    }
}

void solve(){
    cin>>n>>m;
    //初始化
    rep(i,1,n){vis[i]=flag[i]=0;e[i].clear();}
    res=dfncnt=0;
    int u,v;
    rep(i,1,m){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    rep(i,1,n) if(!vis[i]) Tarjan(i,-1);//也可在这重置dfncnt
    cout<<res<<endl;
    rep(i,1,n){
        if(flag[i]) cout<<i<<' ';
    }
    cout<<endl;
}
int main(){
    solve();
}
//P3388 【模板】割点（割顶）
//https://www.luogu.com.cn/problem/P3388

Tarjan求桥(割边)

类似求割点，和割点差不多，只要改一处：$low[v]>dfn[u]$ 就可以了，因为从”>=”变成了”=”，所以不需要考虑祖先节点的问题。

int low[MAXN], dfn[MAXN], iscut[MAXN], dfs_clock;
bool isbridge[MAXN];
vector<int> G[MAXN];
int cnt_bridge;
int father[MAXN];

void tarjan(int u, int fa) {
    father[u] = fa;
    low[u] = dfn[u] = ++dfs_clock;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {//算法核心
                isbridge[v] = true;
                ++cnt_bridge;
            }
        } 
        else if (dfn[v] < dfn[u] && v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}
//摘自OIWIKI
//https://oi-wiki.org/graph/cut/
文章作者: REXWind
文章链接: http://example.com/2020/12/13/graph/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 REXWind !
图论 ACM模板
赏
评论
  目录