学术代码模板（图论部分）

看完点个赞呗！

一.链式前向星

struct Edge {
    int from,to,dis;//next下一条边的编号，to这条边到达的点，dis这条边的长度
} edge[maxm];
int head[maxm],num_edge,n,m,u,v,d;
void add_edge(int from,int to ,int dis) { //添加一条从from到to的距离为dis的单向边
    edge[++num_edge].from=head[from];
    edge[num_edge].to=to;
    edge[num_edge].dis=dis;
    head[from]=num_edge;
}
int main() {
    num_edge=0;
    cin>>n>>m;
    for(i=1--m) {
        cin>>u>>v>>d;
        add_edge(u,v,d);
    }
    for(int i=head[1]; i; i=edge[i].from) {
        u=edge[i].to;
    }
}

二.图的遍历（欧拉路、哈密尔顿环）

主要用于查找问题的解决

三.最短路径算法（Floyed/Dijkstra/Ford/SPFA）

主要用于解决最短距离问题

[1].Dijkstra

b[s]=true;
dis[s]=0;//s为源点 
for(i=1; i<=n-1; i++) { //因为已用去一个点s，所以只有n-1个点
    min1=maxx;
    k=0;
    for(j=1; j<=n; j++) {
        if(!b[j]&&dis[j]<min1) {
            min1=dis[j];
            k=j;
        }
    }//找桥点k
    if(k==0)break;
    b[k]=true;
    for(j=1; j<=n; j++) {
        if(dis[k]+map[k][j]<dis[j]) dis[j]=dis[k]+map[k][j];   //修改以k为桥
    }
}
dis[e];//为要求的终点最小距离

[2].SPFA

dis[s]=0;
team[1]=s;
head=0;
tail=1;
exist[s]=true;
while(head<tail) {
    head++;
    u=team[head];
    exist[u]=false;//出队
    for(j=1; j<=num[u]; j++) {
        if(dis[a[u][j]]>dis[u]+map[u][a[u][j]]) {
            dis[a[u][j]]=dis[u]+map[u][a[u][j]]；
            if(!exist[a[u][j]]) {
                tail++;
                team[tail]= a[u][j];
                exist[a[u][j]]=true;
            }
        }
    }
}

四.并查集

主要用于把相同祖先的元素合并为一个集合问题

for(i=1; i<=n; i++) father[i]=i; //初始化
int find(int x) {
    if(father[x]!=x)father[x]=find(father[x]);//找祖先，路径压缩
    return father[x];
}
main() {
    for(i=1; i<=m; i++) {
        cin>>x>>y;
        int fx=find(x),fy=find(y); //找祖先，路径压缩
        if(fx!=fy)father[fy]=fx; //合并
    }
}

五.最小生成树（Prim/Kruskal）

主要用于解决要求全连通且费用最小问题
[1].Prim

memset(minn,0x7f,sizeof(minn));
minn[1]=0;
MST=0;//以1为起点
memset(vis,false,sizeof(vis));//所有点都没有访问过
for(i=1; i<=n; i++) {
    int k=0;
    for(j=1; j<=n; j++)
        if(!vis[j] && minn[j]<minn[k]) k=j;
    vis[k]=true;
    MST+=minn[k];
    for(j=1; j<=n; j++) {
        if(!vis[j] && map[k][j]<minn[j]) minn[j]= map[k][j];
    }
}

[2].Kruskal

for(i=1; i<=n; i++) father[i]=i; //初始化
MST=0;
k=0;//目前加入的边的个数
sort(edge+1,edge+m+1,cmp);//将所有边从小到大排序
for(i=1; i<=m; i++) {
    int fx=find(edge[i].x),fy=find(edge[i].y); //找祖先，路径压缩
    if(fx!=fy) {
        father[fy]=fx; //合并
        MST+=edge[i].w;
        k++;
        if(k==n-1)break;
    }
}

六.拓扑排序

主要用于排序，找先后关系
[1].

for(i=1; i<=n; i++) {
    if(in[i]==0) {
        stack[++tot]=i;    //把所有入度为0的点入栈 num=0;
    }
}
while(num<n) { //num输出的点<n
    temp=stack[tot];
    cout<<temp<<" ";
    tot--;
    num++;
    for(i=1; i<=out[temp]; i++) {
        in[a[temp][j]]--;//out出度
        if(in[a[temp][j]]==0)  stack[++tot]= a[temp][j]]
        }
}
long Topology_Sort() {        //拓扑排序
    long i,head,tail,u;
    head=tail=0;
    for(i=1; i<=n; i++) {
        if( in[i]==0) {
            list[++tail]=i;
        }
        while(head<tail) {
            u=list[++head];
            cout<<u<<" ";
            for(i=1; i<=n; i++) { //如果已知u的出度out[u]，可以把n改为out[u]
                if(map[i][u]) { //map[u][i]
                    in[i]--;
                    if(!in[i]) {
                        list[++tail]=i;
                    }
                }
            }
        }
        if(tail<n)return 0;
        return 1;
    }
}

[2].

#include<stdio.h>
#include<memory.h>
#define max(a,b) ((a)>(b)?(a):(b))
const long maxn=200;
long n;
long cost[maxn+1],d[maxn+1];
long map[maxn+1][maxn+1];
long list[maxn+1],f[maxn+1],mark[maxn+1];
long ans;
void input() {        //读入
    long i,j;
    scanf("%ld",&n);
    for(i=1; i<=n; i++)
        scanf("%ld",cost+i);
    memset(d,0,sizeof(d));
    for(i=1; i<=n; i++) {
        for(j=1; j<i; j++)
            scanf("%ld",&map[i][j]);
        for(j=i+1; j<=n; j++)
            scanf("%ld",&map[i][j]);
        for(j=1; j<=n; j++)                     //统计点的入度
            d[i]+=map[i][j];
    }
}
long Topology_Sort() {        //拓扑排序
    long i,s,t,u;
    s=t=0;
    for(i=1; i<=n; i++) {
        if(d[i]==0) {
            list[++t]=i;
        }
    }
    while(s<t) {
        u=list[++s];
        for(i=1; i<=n; i++) {
            if(map[i][u]) {
                d[i]--;
                if(!d[i]) {
                    list[++t]=i;
                }
            }
        }
    }
    if(t<n)return 0;
    return 1;
}

void DP() {                        //按拓扑序动态规划
    long i,j,l,u;
    for(i=1; i<=n; i++) {
        u=list[i];
        l=0;
        for(j=1; j<=n; j++) {
            if(map[u][j]) {
                l=max(l,f[j]);
            }
        }
        f[u]=l+cost[u];//f[u]找u的最早完成时间
    }
    ans=0;
    for(i=1; i<=n; i++) {
        ans=max(ans,f[i]);//寻找最早完成时间的最大值，即为整个工程的最早完成时间
    }
}
void Get_Key_Point() {                //寻找关键点
    long i,j,u;
    memset(mark,0,sizeof(mark));
    for(i=1; i<=n; i++)
        if(f[i]==ans)//整工程的最早完成时间，也就是它的最晚完成时间
            mark[i]=1;
    for(i=n; i>=1; i--) { //倒序，如果某子工程的最晚完成时间与最早完成时间相等 ，那
        u=list[i];//它就是关键子工程 即f[j]+cost[u]==f[u]或f[j](最早完成时间)==f[u]-cost[u](最晚完成时间)
        if(mark[u]) {
            for(j=1; j<=n; j++) {
                if(map[u][j] && f[j]+cost[u]==f[u])
                    mark[j]=1;
            }
        }
    }
}
void work() {
    if(!Topology_Sort()) {
        ans=-1;                      //若不能拓扑排序则退出
        return;
    }
    DP();
    Get_Key_Point();
}
void output() {                     //输出
    long i;
    printf("%ld\n",ans);
    if(ans!=-1) {
        for(i=1; i<=n; i++) {
            if(mark[i])
                printf("%ld ",i);
        }
        printf("\n");
    }
}
int main() {
    freopen("project.in","r",stdin);
    freopen("project.out","w",stdout);
    input();
    work();
    output();
    return 0;
}

如果您对本篇博客有任何意见，欢迎提出，期待您的建议！

学术代码模板（图论部分）

原文：https://www.cnblogs.com/jiupinzhimaguan/p/12489364.html