图论汇总 - 洛谷保存站

```cpp
#include <bits/stdc++.h>
using namespace std;
//因本仁石粒有限，所以还有一些算法没有加入
//请务必根据需要适当删减或修改，否则可能出问题 
const int N=1e6+8,M=2e6+8,N2=1e3+5,C=0x3f3f3f3f;
struct G{int x,u,t;} a[M<<1];
int n,m,h[N],dis[N2][N2],cnt=0;
struct spf{int x,fa;};
struct Kru{int x,y,z;} p1[M];
struct Tar{int dfn,low;} p2[N];
int fa[N],ans[N],tar[N];//存算法结果
int w[N],l,stk[N],top=0;//存算法中间过程
bool cmp1(Kru nx,Kru mx){return nx.z<mx.z;}

//联通块和环检测问题
int find(int x){return fa[x]=x==fa[x]?x:find(fa[x]);}
inline void bcj(int x,int y){
    fa[find(y)]=find(x);
}
inline void mem(){for (int i=1;i<=n;i++) fa[i]=i;}

//单源最短路问题
inline void spfa(int s){
    queue <spf> sta;
    memset(ans,C,sizeof(ans));
    memset(w,0,sizeof(w));
    sta.push({s,0});
    w[s]=1;ans[s]=0;
    while (!sta.empty()){
        spf u=sta.front();
        sta.pop();w[u.x]=0;
        for (int i=h[u.x];i;i=a[i].t)
            if (ans[a[i].x]>ans[u.x]+a[i].u){
                ans[a[i].x]=ans[u.x]+a[i].u;
                if (w[a[i].x]==0&&a[i].x!=u.fa) w[a[i].x]=1,sta.push({a[i].x,u.x});}
    }
}

inline void Dijkstra(int s){
priority_queue<pair<int,int> >sta;
    memset(ans,C,sizeof(ans));
    memset(w,0,sizeof(w));
    ans[s]=0,sta.push({0,s}),l=0;
    while (!sta.empty()){
        int u=sta.top().second;
        sta.pop();if (w[u]) continue;
        w[u]=1;l++;if (l==n) break;
        for (int i=h[u];i;i=a[i].t)
            if (ans[a[i].x]>ans[u]+a[i].u)
                ans[a[i].x]=ans[u]+a[i].u,sta.push({-ans[a[i].x],a[i].x});
    }
}

//多源最短路问题
inline void Floyed(){
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

//最小生成树问题
inline int Kruskal(){
    sort(p1+1,p1+1+m,cmp1);
    int k=1;l=0;
    for (int i=1;i<=m;i++){
        if (find(p1[i].x)!=find(p1[i].y))
            bcj(p1[i].x,p1[i].y),l+=p1[i].z,k++;
        if (k==n) break;
    }if (k<n) l=-1;mem();
    return l;
}

inline int Prim(){
priority_queue<pair<int,int> >sta;
    int x,u,cnt=0;l=0;sta.push({0,1});
    memset(w,0,sizeof(w));
    while (!sta.empty()){
        x=sta.top().first;
        u=sta.top().second;
        sta.pop();
        if (w[u]) continue;
        w[u]=1;l-=x;cnt++;
        if (cnt==n) break;
        for (int i=h[u];i;i=a[i].t)
            if (!w[a[i].x]) sta.push({-a[i].u,a[i].x});
    }if (cnt<n) l=-1;
    return l;
}

//强联通分量问题
void tarjan(int x){
    p2[x].dfn=p2[x].low=++l;
    stk[++top]=x;w[x]=1;
    for (int i=h[x];i;i=a[i].t){
        if (!p2[a[i].x].dfn) tarjan(a[i].x);
        if (w[a[i].x]) p2[x].low=min(p2[x].low,p2[a[i].x].low);
    }
    if (p2[x].dfn==p2[x].low){
        int y=0,sz=0;
        while (x!=y) y=stk[top--],sz++,w[y]=0;
        if (sz==1) tar[x]=1;
    }
}
inline void Tarjan(){l=0;
    memset(w,0,sizeof(w));
    for (int i=1;i<=n;i++) if (!p2[i].dfn) tarjan(i);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    memset(dis,C,sizeof(dis));
	cin >>n>>m;
	for (int i=1;i<=n;i++) dis[i][i]=0;
	mem();
	for (int i=1,x,y,z;i<=m;i++){
	    cin >>x>>y>>z;
	    p1[i]={x,y,z};
	    dis[x][y]=dis[y][x]=min(dis[x][y],z);
	    cnt++;a[cnt]={y,z,h[x]};h[x]=cnt;
	    cnt++;a[cnt]={x,z,h[y]};h[y]=cnt;
	}
	
	return 0;
}
```

正在渲染内容...