历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

最短路、最小生成树和图遍历

作者：

Im_iceman , 2021-08-24 15:51:59 , 所有人可见 , 阅读 328

2

1

最短路

Dijkstra 算法

时间复杂度 $\operatorname{O(n^2)}$
堆优化时间复杂度 $\operatorname{O(mlog_2n)}$
空间复杂度 $\operatorname{O(n^2)}$
代码：

// 朴素算法
int g[N][N];
int d[N];
bool vis[N];
void dj(int s) {
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    d[s]=0;
    for(int i=1;i<=n;i++) {
        int u=-1;
        int Min=0x3f3f3f3f;
        for(int j=1;j<=n;j++) {
            if(vis[j]==0 && d[j]<Min) { // 找当前最短路最小的点
                Min=d[j];
                u=j;
            }
        }
        if(u==-1) {
            return ;
        }
        vis[u]=1;
        for(int v=1;v<=n;v++) { // 用该点松弛与其相连的点
            if(vis[v]==0 && g[u][v]!=0x3f3f3f3f && d[v]>d[u]+g[u][v]) {
                d[v]=d[u]+g[u][v];
            }
        }
    }
}

//堆优化
int e[M];
int w[M];
int nx[M];
int h[N];
int idx;

int d[N];
bool vis[N];

void dj(int s) {
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    priority_queue< pair<int,int> >q;
    q.push(make_pair(0,s));
    while(q.size()!=0) {
        int x=q.top().second; // 当前最短路最小的点
        q.pop();
        if(vis[x]==1) {
            continue;
        }
        vis[x]=1;
        for(int i=h[x];i;i=nx[i]) { // 松弛操作
            int y=e[i];
            int z=w[i];
            if(d[y)>d[x]+z) {
                d[y]=d[x]+z; 
                q.push({-d[y],y});
            }
        }
    }
}

//手写堆优化
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;

const int N=150010;
const int M=150010;

PII h[N];
int cnt=0;

int e[M];
int w[M];
int nx[M];
int he[N];
int idx;

int d[N];
bool vis[N];

int n,m;

void add(int x,int y,int z) { //加边
    e[++idx]=y;
    w[idx]=z;
    nx[idx]=he[x];
    he[x]=idx;
}

void down(int u) { //向下调整
    int t=u;
    int lc=t*2;
    int rc=lc+1;
    if(lc<=cnt && h[lc].first<h[t].first) {
        t=lc;
    }
    if(rc<=cnt && h[rc].first<h[t].first) {
        t=rc;
    }
    if(u!=t) {
        swap(h[u],h[t]);
        down(t);
    }
}
void up(int u){ //向上调整
    while(u){
        if(u/2>=1 && h[u/2].first>h[u].first){
            swap(h[u/2],h[u]);
        }
        u/=2;
    }
}
void build_heap() { //建堆
    for(int i=cnt/2;i;i--) {
        down(1);
    }
}
void pop() { //弹出堆顶
    h[1]=h[cnt];
    cnt--;
    down(1);
}
void push(PII x) { //插入元素
    h[++cnt]=x;
    up(cnt);
}
PII top() { //返回堆顶
    return h[1];
}
void dj(int s) {
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    d[s]=0;
    push(make_pair(0,s));
    while(cnt>0) {
        int x=top().second;
        pop();
        if(vis[x]==1) {
            continue;
        }
        vis[x]=1;
        for(int i=he[x];i;i=nx[i]) {
            int y=e[i];
            int z=w[i];
            if(d[y]>d[x]+z) {
                d[y]=d[x]+z;
                push(make_pair(d[y],y));
            }   
        }
    }
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++) {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
    }
    dj(1);
    if(d[n]>=0x3f3f3f3f) {
        printf("-1");
    }
    else printf("%d",d[n]);
    return 0;
}

Bellman-Ford 算法

时间复杂度 $\operatorname{O(nm)}$
空间复杂度 $\operatorname{O(m)}$
代码：

struct node {
    int x,y,z;
}g[M]; //注意，这里不是邻接表，但这种方法适合Bellman-Ford

int d[N];

int n,m;

void bellman(int s) {
    memset(d,0x3f,sizeof d);
    d[s]=0;
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=m;i++) {
            int x=g[i].x;
            int y=g[i].y;
            int z=g[i].z;
            if(d[y]>d[x]+z) { //松弛操作
                d[y]=d[x]+z;
            }
        }
    }
}

SPFA 算法

时间复杂度 最优 $\operatorname{O(m)}$ 最坏 $\operatorname{O(nm)}$
空间复杂度 $\operatorname{O(n)}$

int d[N];
bool inque[N];
int e[M];
int w[M];
int nx[M];
int h[N];

int idx=0;
int n,m;

void add(int x,int y,int z) {
    e[++idx]=y;
    w[idx]=z;
    nx[idx]=h[x];
    h[x]=idx;
}

void spfa(int s)
{
    memset(d,0x3f,sizeof d);
    queue<int>q;
    d[s] = 0;
    q.push(s);
    inque[s]=1;
    while (q.size()!=0) {
        int x = q.front();
        q.pop();
        vis[x]=0;
        for (int i = h[x]; i ; i = nx[i]) {
            int y = e[i];
            if (d[y]>d[x]+w[i]) {
                d[y]=d[x]+w[i];
                if (!inque[y]) {
                    q.push(y);
                    inque[y]=1;
                }
            }
        }
    }
}

//SPFA判断负环

void add(int x,int y,int z) {
    e[++idx]=y;
    w[idx]=z;
    nx[idx]=h[x];
    h[x]=idx;
}

void re() {
    for(int i=1;i<=n;i++) {
        add(0,i,0);
        add(i,0,0);
    }
}

bool spfa(int s) {
    int cnt[N];
    queue<int> q;
    memset(spfa_d, 0x3f, sizeof spfa_d);
    memset(cnt,0,sizeof cnt); //不要忘记初始化
    cnt[s]=1; //这也别忘了
    for(int i=1;i<=n;i++) {
        q.push(i);
        inque[i]=1;
    }
    while (!q.empty()) {
        int x=q.front();
        q.pop();
        inque[x]=0;
        for (int i=h[x]; i; i=nx[i]) {
            int y = e[i];
            if (spfa_d[y] > spfa_d[x] + w[i]) {
                spfa_d[y] = spfa_d[x] + w[i];
                cnt[y]=cnt[x]+1;
                if (cnt[y]>n+1) return true;
                if (!inque[y]) {
                    inque[y] = 1;
                    q.push(y);
                }
            }
        }
    }
    return false;
}

注意，该算法比赛时易被卡成 $\operatorname{O(nm)}$

Floyd 算法

时间复杂度 $\operatorname{O(n^3)}$
空间复杂度 $\operatorname{O(n^2)}$
代码：

int d[N][N];
//不要写成 i,j,k，DP先阶段，后状态
for(int k=1;k<=n;k++) { 
    for(int i=1;i<=n;i++) { 
        for(int j=1;j<=n;j++) { 
            d[i][j]=min(d[i)[j],d[i][k]+d[k][j]);
        }
    }
}

Johnson 全源最短路算法

时间复杂度 $\operatorname{O(n(n+m)log_2n)}$
空间复杂度 $\operatorname{O(n^2)}$

//调试了6个小时的代码
#include<bits/stdc++.h>
using namespace std;

const int N=3010;
const int M=9010;

//链式前向星
int h[N];
int e[M];
int w[M];
int nx[M];
int idx;

//spfa的变量
int spfa_d[N];
bool inque[N];

//dijkstra的变量
int d[N];
int dis[N][N];
bool vis[N];

//其他变量
int n,m;


//链式前向星
void add(int x,int y,int z) {
    e[++idx]=y;
    w[idx]=z;
    nx[idx]=h[x];
    h[x]=idx;
}

//spfa判断负环
bool spfa(int s) {
    int cnt[N];
    queue<int> q;
    memset(spfa_d, 0x3f, sizeof spfa_d);
    memset(cnt,0,sizeof cnt); //不要忘记初始化
    cnt[s]=1; //这也别忘了
    for(int i=1;i<=n;i++) {
        q.push(i);
        inque[i]=1;
    }
    while (!q.empty()) {
        int x=q.front();
        q.pop();
        inque[x]=0;
        for (int i=h[x]; i; i=nx[i]) {
            int y = e[i];
            if (spfa_d[y] > spfa_d[x] + w[i]) {
                spfa_d[y] = spfa_d[x] + w[i];
                cnt[y]=cnt[x]+1;
                if (cnt[y]>n+1) return true;
                if (!inque[y]) {
                    inque[y] = 1;
                    q.push(y);
                }
            }
        }
    }
    return false;
}

//dijkstra求最短路
void dj(int s) {
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    d[s]=0;
    priority_queue< pair<int,int> >q;
    q.push({0,s});
    while(q.size()!=0) {
        int x=q.top().second;
        q.pop();
        if(vis[x]==1) {
            continue;
        }
        vis[x]=1;
        for(int i=h[x]; i; i=nx[i]) {
            int y=e[i];
            int z=w[i];
            if(d[y]>d[x]+z) {
                d[y]=d[x]+z;
                q.push({-d[y],y});
            }
        }
    }
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=1; i<=m; i++) {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
    }

    for(int i=1; i<=n; i++) { //加边
        add(0,i,0);
    }
    if(spfa(0)==1) {
        printf("-1"); //判断负环
        return 0;
    }
    for(int k=1; k<=n; k++) {
        for(int i=h[k]; i; i=nx[i]) {
            int y=e[i];
            w[i]+=spfa_d[k]-spfa_d[y]; //修改边的权值
        }
    }
    for(int i=1; i<=n; i++) {
        dj(i);
        long long ans=0;
        for(int j=1; j<=n; j++) {
            dis[i][j]=d[j]+spfa_d[j]-spfa_d[i]; //用Dijkstra走最短路
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            printf("%d ",dis[i][j]);
        }
        printf("\n");
    }
    return 0;
}

最小生成树

Prim 算法

时间复杂度 $\operatorname{O(n^2)}$
空间复杂度 $\operatorname{O(n^2)}$
代码：

int a[N][N];
int d[N];
bool vis[N];

void prim() {
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    d[1]=0;
    for(int i=1;i<=n;i++) {
        int x=0;
        for(int j=1;j<=n;j++) {
            if(vis[j]==0 && (x==0 || d[j]<d[x])) x=j;
        }
        vis[x]=1;
        for(int y=1;y<=n;y++) {
            if(vis[y]==0) {
                d[y]=min(d[y],a[x][y);
            }
        }
    }
}

Kruskal 算法

时间复杂度 $\operatorname{O(mlog_2m)}$
空间复杂度 $\operatorname{O(max(n,m))}$
代码：

struct node {
    int x,y,z;
}g[M];

int father[N];

int ans=0;
int cnt=0;

int Find(int x) {
    if(x==father[x]) {
        return x;
    }
    return father[x]=Find(father[x); //并查集
}
bool cmp(node a,node b) {
    return a.z<b.z;
}
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) {
        father[i]=i;
    }
    for(int i=1;i<=m;i++) {
        scanf("%d %d %d",&g[i].x,&g[i].y,&g[i].z);
    }
    sort(g+1,g+1+m,cmp);
    for(int i=1;i<=m;i++) {
        int x=g[i].x;
        int y=g[i].y;
        int z=g[i].z;
        int fx=Find(x);
        int fy=Find(y);
        if(fx==fy) { //若加入边会形成环，那么跳过这条边
            continue;
        }
        father[fx]=fy;
        ans+=z;
        cnt++;
        if(cnt==n-1) { // 最多n-1条边
            break;
        }
    }
    printf("%d",ans);
}

图遍历

DFS算法

void dfs(int x)  {
    if(vis[x]) return ;
    vis[x]=1;
    for(int i=h[x];i;i=nx[i]) {
        int y=e[i];
        dfs(y);
    }
}

BFS算法

void bfs(int s) {
    vis[s]=1;
    queue<int>q;
    q.push(s);
    while(q.size()) {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=nx[i]) {
            int y=e[i];
            if(vis[y]==0) {
                q.push(y);
            }
        }
    }
}

0 评论

App 内打开