头像

PHI6




离线:52分钟前


活动打卡代码 AcWing 852. spfa判断负环

PHI6
1小时前
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N],cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

bool  spfa()
{
    //此处不需要初始化因为只是求是否有负边
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
       st[i]=true;
       q.push(i);
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[t])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }  
    return false;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    if(spfa()) puts("Yes");
    else puts("No");

    return 0;
}




PHI6
1小时前

题目思路

求负环,我们只需要增加一个统计最短路边数的数组cnt,当cnt>=n的时候,就说明至少有n+1个点根据抽屉原理,必有两个重复的点也就是必有一个环。

dist[x]=dist[t]+w[i];
cnt[x]=cnt[t]+1;

算法1

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N],cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

bool  spfa()
{
    //此处不需要初始化因为只是求是否有负边
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
       st[i]=true;
       q.push(i);
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];//注意此处是抓走过的边
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[t])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }  
    return false;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    if(spfa()) puts("Yes");
    else puts("No");

    return 0;
}



活动打卡代码 AcWing 851. spfa求最短路

PHI6
4小时前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)//把以c为权值的b插入a链
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int sfpa()
{
    memset(dist,0x3f,sizeof dist);dist[1]=0;

    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i= h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=sfpa();
    if(t==-1)puts("impossible");
    else cout<<t<<endl;
    return 0;
}




PHI6
4小时前

SPFA算法

本质是对Bellman-Ford算法的一个优化

利用宽搜做优化

queue<-起点1入队
while queue 不空
    取出队头(t<-q.front);q.pop();
    更新一下t的所有出边;
    queue<-b;

算法1

算法思路不难,y总都是直接用Dijkstra最短路改的,本质也就是用了队列优化for loop。
在此直接记录一下关于sfpa函数的思路,其余的也就是模板,背一背即可。

1.初始化dist数组(十分重要,虽然就两个语句),随后进行队列的初始化,将队头也就是1插入队列,更新state数组为ture也就是已被使用。
2.for loop一遍即可,但是关键就在这一步,用j字母存放当前边,比较通过当前边的距离和通过t这个点的距离哪个小,更新到j的dist数组中,随后检查是否被使用,若没有,加入队列。

关键语句解读

理解这个语句之前,要知道一些东西,比如h是指头结点,ne指的next数组也就是头结点的下一个节点,e指的是存放该边数字的数组,w存的权值大小。

 for(int i= h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }

首先,把h的值取出来,在e中找到h真正是第几号结点。
在进行下一步时,我们要明确t是指向的队头结点,i指向的是链队头结点。
随后,进行比较,这个比较是指从t也就是1直接到j的路径和1通过i到j的路径的大小
更新,判断是否需要插入,不需要则进行下一步。

样例详细图解如下:
QQ图片20210122154504.jpg

总体模拟的就是从1开始往后走往后找路径的过程,若有更近的则进行更新,需要注意的是idx默认由0开始,最开始插入的链为0。
为什么是dist[j]=dist[t]+w[i]?
因为t代表的是从初始结点往后延伸的路径,t是指与初始结点直接相连的点的路径,w是指走该路径的代价需要往回找,比如1->2的代价存在w[0]里面,以此类推。

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=1e5+10;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)//把以c为权值的b插入a链
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int sfpa()
{
    memset(dist,0x3f,sizeof dist);dist[1]=0;

    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;

        for(int i= h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=sfpa();
    if(t==-1)puts("impossible");
    else cout<<t<<endl;
    return 0;
}




PHI6
6小时前

Bellman-Ford算法

可以求出是否存在负权边的问题但时间复杂度较高

算法过程

更新过程叫:松弛操作
for loop n 次
备份一下//因为边数有限制,可能更新后的边数太长不能用
    for 所有边a,b,w(a->b的边权值为w)
    更新所有边dist[b]=min(dist[b],dist[a]+w;
    //看看当前点通过a到b的距离和直接到b的距离哪个短

循环n次后一定满足dist[b]<=dist[a]+w;//三角不等式

某些题只能用Bellman-Ford算法

比如:输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。


算法1

基本按照y总讲的过程就能实现,比起之前的Dijkstra简单的多,甚至可以直接定义一个结构体进行操作。

主要核心在于以下几条语句:

memset(dist,0x3f,sizeof dist);dist[1]=0;

初始化,不难,但容易遗忘

memcpy(backup,dist,sizeof dist);

防止串联,所以要进行一个备份,因为不知道能不能用这个长度的距离更新。有点类似于计网里面的慢收敛。

for(int j=0;j<m;j++)
        {
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }

最关键的更新语句,也类似于Dijkstra里面的更新,主要记住有几条边更新几次,但是是利用backup里面的内容更新的,因为最多就能走k条边。

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,M=1e5+10;

int n,m,k;
int dist[N],backup[N];

struct Edge
{
    int a,b,w;
}edge[M];

int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);dist[1]=0;//初始化相当重要,两条语句缺一不可
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i]={a,b,w};
    }
    int t=bellman_ford();
    if(t==-1)puts("impossible");
    else cout<<t<<endl;

    return 0;
}



PHI6
6小时前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,M=1e5+10;

int n,m,k;
int dist[N],backup[N];

struct Edge
{
    int a,b,w;
}edge[M];

int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);dist[1]=0;//初始化相当重要,两条语句缺一不可
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++)
        {
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i]={a,b,w};
    }
    int t=bellman_ford();
    if(t==-1)puts("impossible");
    else cout<<t<<endl;

    return 0;
}



PHI6
1天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int,int> PII;
const int N=150010;

int n,m;
int e[N],h[N],ne[N],w[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int dijkstra_h()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    //优先队列,用来模拟堆,本质上还是队列,greater代表升序,也就是小根堆。
    priority_queue<PII,vector<PII>,greater<PII>> heap;

    heap.push({0,1});//第一次先放入起点

    while(heap.size())
    {
        auto t=heap.top();//优先队列升序顶最小,每次取出来当前距离最小的点
        heap.pop();
        int ver=t.second,distance = t.first;//ver存放当前点的编号,distance存放当前点的距离代价
        if(st[ver]) continue;//如果已经更新过,那就是冗余备份,跳过
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])//否则就借着这个点更新其他的点
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    int t=dijkstra_h();
    cout<<t<<endl;
    return 0;
}



PHI6
1天前

堆优化版的Dijkstra算法

适用于稀疏图

解题思路

1.因为是模拟的堆所以先用的链队存储已有的路径,所以就有e啊ne啊idx之类的东西,都是模板啦自己记一记,随后再add一下,就是在链表中加入已知路径,这也是模板!!!
2.初始化链队数组,将所有的路径输入,调用优化的Dijkstra函数。
3.优化的Dijkstra函数首先将距离数组初始化,把第一个的距离设为0。
4.关键一步来了,由于升序优先队列模拟的是小根堆,所以堆顶一定是最小距离,取出这个最小距离与所有节点的距离进行更新,若到达该点的距离小于通过当前更新点的距离,那么把该点更新后插入队列。
5.如果最后距离无穷大,那么不存在最短路径。


算法1

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int,int> PII;
const int N=150010;

int n,m;
int e[N],h[N],ne[N],w[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int dijkstra_h()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    //优先队列,用来模拟堆,本质上还是队列,greater代表升序,也就是小根堆。
    priority_queue<PII,vector<PII>,greater<PII>> heap;

    heap.push({0,1});//第一次先放入起点

    while(heap.size())
    {
        auto t=heap.top();//优先队列升序顶最小,每次取出来当前距离最小的点
        heap.pop();
        int ver=t.second,distance = t.first;//ver存放当前点的编号,distance存放当前点的距离代价
        if(st[ver]) continue;//如果已经更新过,那就是冗余备份,跳过
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])//否则就借着这个点更新其他的点
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    int t=dijkstra_h();
    cout<<t<<endl;
    return 0;
}



PHI6
1天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;

int n,m;
int g[N][N];
int dist[N];//存放当前的最短距离
bool st[N];//看看当前最短路径是否已经确定

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//在所有st[j]=false的点当中找到距离最小的点
                t=j;

        // if(t==n) break;

        st[t]=true;

        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}


int main()
{
    scanf("%d%d",&n,&m);

    memset(g,0x3f,sizeof g);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);//只保留最短的那条边,因为ab之间可能有多条边
    }

    int t=dijkstra();

    printf("%d\n",t);

    return 0;
}



PHI6
1天前

最短路问题

单源最短路:从一个点到其他所有点的最短距离

  1. 所有边都是正权值

朴素Dijkstra算法O(N^2) ->适合稠密图,因为与边数无关

堆优化版的Dijkstra算法O(mlogn) ->适合稀疏图

  1. 存在负权边

Bellman-Frof O(mn)

SPFA O(m) ->一般情况下是O(m),最坏O(mn)。

多源汇最短路:源指的起点,汇指终点。

Floyd算法 O(n^3)

朴素版Dijkstra算法

设置一个s数组存放已经确定是最短路径的点
1. 初始化距离 dist[1]=0,dist[i]=+无穷//因为只有起点的距离可以确定为1
2. for loop n次:i从1->n
    t<-找到不在s中的距离最近的点
    s<-t
    用t来更新其他所有点的距离


算法1

思路步骤就是
1.先对整个数组进行初始化,让所有的距离都为无穷这种操作。
2.因为题目说了有环路和有重边,所以我们每次只保留最小距离的边即可,因为求最短距离。
3.进入关键算法,因为是从单源开始所以不需要参数,起始点永远是1。
4.将距离矩阵初始化为无穷,从1开始遍历所有结点,在未确定(st[j]==false)的点中寻找距离最小的点,如果发现当前点比j的距离大那么就进行交换。当该点交换后或者本身就是最短距离点,那么就对st进行“改真”操作。
5.for loop一下整个dist数组,更新到最短的距离也就是比较直接到的最短距离与通过其余节点到达的最短距离大小,这也是为什么Dijkstra不是局部最优算法的原因。

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;

int n,m;
int g[N][N];
int dist[N];//存放当前的最短距离
bool st[N];//看看当前最短路径是否已经确定

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//在所有st[j]=false的点当中找到距离最小的点
                t=j;

        // if(t==n) break;

        st[t]=true;

        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}


int main()
{
    scanf("%d%d",&n,&m);

    memset(g,0x3f,sizeof g);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);//只保留最短的那条边,因为ab之间可能有多条边
    }

    int t=dijkstra();

    printf("%d\n",t);

    return 0;
}