Skip to content

Latest commit

 

History

History
250 lines (207 loc) · 7.05 KB

3-图论.md

File metadata and controls

250 lines (207 loc) · 7.05 KB

图论

存图

  • 前向星
  • 注意边数开够
int Head[N], Ver[N*2], Next[N*2], Ew[N*2], Gtot=1;
inline void graphinit(int n) {Gtot=1; for(int i=1; i<=n; ++i) Head[i]=0;}
inline void edge(int u, int v, int w=1) {Ver[++Gtot]=v; Next[Gtot]=Head[u]; Ew[Gtot]=w; Head[u]=Gtot;}
#define go(i,st,to) for (int i=Head[st], to=Ver[i]; i; i=Next[i], to=Ver[i])

最短路

Dijkstra

  • 非负权图
namespace DIJK{//适用非负权图 满足当前dist最小的点一定不会再被松弛
	typedef pair<long long,int> pii;
	long long dist[N];//存最短路长度
	bool vis[N];//记录每个点是否被从队列中取出  每个点只需第一次取出时扩展
	priority_queue<pii,vector<pii>,greater<pii> >pq;//维护当前dist[]最小值及对应下标 小根堆

	inline void dijk(int s,int n){//s是源点 n是点数
		while(pq.size())pq.pop();for(int i=1;i<=n;++i)dist[i]=INFLL,vis[i]=0;//所有变量初始化
		dist[s]=0;pq.push(make_pair(0,s));
		while(pq.size()){
			int now=pq.top().second;pq.pop();
			if(vis[now])continue;vis[now]=1;
			go(i,now,to){
				const long long relx(dist[now]+Ew[i]);
				if(dist[to]>relx){dist[to]=relx;pq.push(make_pair(dist[to],to));}//松弛
			}
		}
	}
}

LCA

  • 倍增求lca
  • 数组开够
namespace LCA_Log{
	int fa[N][22],dep[N];
	int t,now;
	void dfs(int x){
		dep[x]=dep[fa[x][0]]+1;
		go(i,x,to){
			if(dep[to])continue;
			fa[to][0]=x;for(int j=1;j<=t;++j)fa[to][j]=fa[fa[to][j-1]][j-1];
			dfs(to);
		}
	}

	//初始化接口
	inline void lcainit(int n,int rt){//记得初始化全部变量
		now=1;t=0;while(now<n)++t,now<<=1;
		for(int i=1;i<=n;++i)dep[i]=0,fa[i][0]=0;
		for(int i=1;i<=t;++i)fa[rt][i]=0;
		dfs(rt);
	}

	//求lca接口
	inline int lca(int u,int v){
		if(dep[u]>dep[v])swap(u,v);
		for(int i=t;~i;--i)if(dep[fa[v][i]]>=dep[u])v=fa[v][i];
		if(u==v)return u;
		for(int i=t;~i;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
		return fa[u][0];
	}
}

连通性

有向图强联通分量

  • tarjan $O(n)$ 
namespace SCC{
	int dfn[N],clk,low[N]; 
	bool ins[N];int sta[N],tot; //栈  存正在构建的强连通块
	vector<int>scc[N];int c[N],cnt;//cnt为强联通块数 scc[i]存放每个块内点 c[i]为原图每个结点属于的块
	void dfs(int x){
	    dfn[x]=low[x]=(++clk);//low[]在这里初始化
	    ins[x]=1;sta[++tot]=x;
	    go(i,x,to){
	        if(!dfn[to]){dfs(to);low[x]=min(low[x],low[to]);}//走树边
	        else if(ins[to])low[x]=min(low[x],dfn[to]);//走返祖边
	    }
	    if(dfn[x]==low[x]){//该结点为块的代表元
	        ++cnt;int u;
	        do{u=sta[tot--];ins[u]=0;c[u]=cnt;scc[cnt].push_back(u);}while(x!=u);
	    }  
	}
	inline void tarjan(int n){//n是点数
	    for(int i=1;i<=cnt;++i)scc[i].clear();//清除上次的scc 防止被卡MLE
	    for(int i=1;i<=n;++i)dfn[i]=ins[i]=0;tot=clk=cnt=0;//全部变量初始化
	    for(int i=1;i<=n;++i)if(!dfn[i])dfs(i);
	    for(int i=1;i<=n;++i)c[i]+=n;//此行(可以省略)便于原图上加点建新图 加新点前要初始化Head[]=0
	}
}

二分图匹配

匈牙利算法求二分图无权最大匹配

  • 复杂度O(nm)
#include<bits/stdc++.h>
using namespace std;
namespace Hungary{
    const int N=1000009;
    //图中应储存左部到右部的边  左点编号1..n  右点编号1..m
    int Head[N],Ver[N*2],Next[N*2],Gtot=1;  //注意边数开够
    inline void graphinit(int n){Gtot=1;for(int i=1;i<=n;++i)Head[i]=0;}
    inline void edge(int u,int v){Ver[++Gtot]=v,Next[Gtot]=Head[u],Head[u]=Gtot;}
    #define go(i,st,to) for(int i=Head[st],to=Ver[i];i;i=Next[i],to=Ver[i]) //st是左点，to是st能到达的右点

    int match[N],vis[N];//右点的的匹配点和访问标记

    bool dfs(int x){//x是左点
    	go(i,x,to)if(!vis[to]){
    		vis[to]=1;
    		if(!match[to]||dfs(match[to])){
    			match[to]=x;return 1;
    		}
    	}
    	return 0;
    }

    inline int ask(int n,int m){//左点数和右点数 返回最大匹配数
    	for(int i=1;i<=m;++i)match[i]=0;int res=0;
    	for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j)vis[j]=0;
            res+=dfs(i);
        }
    	return res;
    }
}

KM算法求二分图带权最大匹配

  • 要求该图存在完美匹配 该算法将最大化完美匹配的权值和

  • 复杂度 O(n^3)

  • naive的写法复杂度为O((n^2)m) 在完全图上会退化至O(n^4) luogu P6577

#include<bits/stdc++.h>
using namespace std;
namespace KM{
    const int N=509;
    const long long INFLL=0x3f3f3f3f3f3f3f3fll;//注意INF应足够大 至少远大于n*n*Max{W}
    
    int n;//左右点数均为n 标号均为1..n
    int w[N][N];//邻接矩阵存边权
    bool r[N][N];//记录i j之间是否有边连接 完全图/非0权图则不必要

    inline void init(){//记得重写初始化
    	int m;scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;++i){
    		int u,v,wt;scanf("%d%d%d",&u,&v,&wt);
    		w[u][v]=wt;r[u][v]=1;
    	}
    }

    long long la[N],lb[N],upd[N];//左右顶标 每个右点对应的最小delta 要开longlong
    int last[N];//每个右点对应的回溯右点
    bool va[N],vb[N];
    int match[N];//每个右点对应的左匹配点
    bool dfs(int x,int fa){
    	va[x]=1;
    	for(int y=1;y<=n;++y)if(r[x][y]&&!vb[y]){
    		const long long dt=la[x]+lb[y]-w[x][y];
    		if(dt==0){//相等子图
    			vb[y]=1;last[y]=fa;
    			if(!match[y]||dfs(match[y],y)){
    				match[y]=x;
    				return 1;
    			}
    		}else if(upd[y]>dt){//下次dfs直接从最小delta处开始 
    			upd[y]=dt;
    			last[y]=fa;//用last回溯该右点的上一个右点以更新增广路
    		}
    	}
    	return 0;
    }

    inline void KM(){
    	for(int i=1;i<=n;++i){//初始化顶标
    		la[i]=-INFLL;lb[i]=0;
    		for(int j=1;j<=n;++j)if(r[i][j])la[i]=max(la[i],(long long)w[i][j]);
    	}
    	for(int i=1;i<=n;++i){//尝试给每一个左点匹配上右点 匹配失败则扩展相等子图重试至成功
    		memset(va,0,sizeof va);//注意复杂度
    		memset(vb,0,sizeof vb);
    		memset(last,0,sizeof last);
    		memset(upd,0x3f,sizeof upd);
    		int st=0;match[0]=i;//给起点i连一个虚右点 标号为0
    		//不断尝试将右点st从已有的匹配中解放 以获得增广路
    		while(match[st]){//当st到达非匹配右点直接退出
    			long long delta=INFLL;
    			if(dfs(match[st],st))break;//st的左点匹配到了新的右点则退出
    			for(int j=1;j<=n;++j)
    				if(!vb[j]&&upd[j]<delta){//下次从最小的delta处开始DFS
    					delta=upd[j];
    					st=j;
    				}
    			for(int j=1;j<=n;++j){//将交错树上的左顶标加delta 右顶标减delta 使更多的边转为相等边
    				if(va[j])la[j]-=delta;
    				if(vb[j])lb[j]+=delta;
    					else upd[j]-=delta;//小问题:这里在干啥 每次修改顶标后重新计算upd是否可行
    			}
    			vb[st]=1;
    		}
    		while(st){//更新增广路
    			match[st]=match[last[st]];
    			st=last[st];
    		}
    	}

    	long long ans=0;
    	for(int i=1;i<=n;++i)ans+=w[match[i]][i];
    	printf("%lld\n",ans);
    	for(int i=1;i<=n;++i)printf("%d%c",match[i]," \n"[i==n]);
    }
    //signed main(){init();KM();return 0;}
}