AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

spfa判断负环的应用

2023-11-10 200
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： spfa判断负环的应用

 


1.虫洞 Wormholes（裸spfa判断负环问题）

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

1. #in#include<bits/stdc++.h>
using namespace std;
int n,m,W;
const int N=510,M=5210;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],cnt[N],q[N];//cnt记录是某个点经过的边数
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()
{
    memset(st,0,sizeof st);//情况上一层的状态
    memset(cnt,0,sizeof cnt);//情况上一层的状态
    int hh=0,tt=0;
    for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中
    while(hh!=tt)
    {
        int t=q[hh++];
        st[t]=false;//标记这个点已经不在队列中了
        if(hh==N) hh=0;//循环数组
        for(int i=h[t];~i;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;//假如边数大于等于n，说有环的存在，而且我们是按照最小距离更新，所有是负环
                if(!st[j])//假如不在队列中则加到队列中
                {
                    q[tt++]=j;
                    st[j]=true;
                    if(tt==N) tt=0;
                }
            }
        }
    }
    return false;//反之没负环
}
void solve()
{
    memset(h,-1,sizeof h);//初始化
    idx=0;
    cin>>n>>m>>W;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    while(W--)//假如是虫洞，就建立负边
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,-c);
    }
    if(spfa()) puts("YES");//假如有负环
    else puts("NO");
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
  return 0;
}

栈优化 

#include<bits/stdc++.h>
using namespace std;
int n,m,W;
const int N=510,M=5210;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],cnt[N],q[N];//cnt记录是某个点经过的边数
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()
{
    memset(st,0,sizeof st);//情况上一层的状态
    memset(cnt,0,sizeof cnt);//情况上一层的状态
    int tt=0;
    for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中
    while(tt!=0)
    {
        int t=q[--tt];
        st[t]=false;//标记这个点已经不在队列中了
        for(int i=h[t];~i;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;//假如边数大于等于n，说有环的存在，而且我们是按照最小距离更新，所有是负环
                if(!st[j])//假如不在队列中则加到队列中
                {
                    q[tt++]=j;
                    st[j]=true;
                }
            }
        }
    }
    return false;//反之没负环
}
void solve()
{
    memset(h,-1,sizeof h);//初始化
    idx=0;
    cin>>n>>m>>W;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    while(W--)//假如是虫洞，就建立负边
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,-c);
    }
    if(spfa()) puts("YES");//假如有负环
    else puts("NO");
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
  return 0;
}

2.观光奶牛（01分数规划+spfa判断负环）

361. 观光奶牛 - AcWing题库

朴素spfa

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010,M=5010;
int h[N],e[M],ne[M],idx;
double dist[N],wf[N],wt[M];
int cnt[N],q[N];//cnt记录是某个点经过的边数
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,wt[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(double mid)
{
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    int hh=0,tt=0;
    for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;//循环数组
        st[t]=false;//标记这个点已经不在队列中了
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+wf[t]-mid*wt[i])//假如负和01分数规划分析的
            {
               dist[j]=dist[t]+wf[t]-mid*wt[i];//则更新
                cnt[j]=cnt[t]+1;//更新所走过的边数
                if(cnt[j]>=n) return true;//假如边数大于等于n，说有环的存在，而且我们是按照01分数规划更新，所有是负环
                if(!st[j])//假如不在队列中则加到队列中
                {
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
    return false;//反之没负环
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) cin>>wf[i];
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    double l=0,r=1000;//分析最大可能是1000，最小是0
    while(r-l>1e-4)//二分答案，因为要输出两位小数，则精度得是两位小数，则二分则是多两位是4位
    {
        double mid=(l+r)/2;
        if(spfa(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n",l);
  return 0;
}


栈优化 

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1010,M=5010;
int h[N],e[M],ne[M],idx;
double dist[N],wf[N],wt[M];
int cnt[N],q[N];//cnt记录是某个点经过的边数
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,wt[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(double mid)
{
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    int tt=0;
    for(int i=1;i<=n;i++) q[tt++]=i,st[i]=true;//把所有点入队，并标记在队列中
    while(tt!=0)
    {
        int t=q[--tt];
        st[t]=false;//标记这个点已经不在队列中了
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+wf[t]-mid*wt[i])//假如负和01分数规划分析的
            {
               dist[j]=dist[t]+wf[t]-mid*wt[i];//则更新
                cnt[j]=cnt[t]+1;//更新所走过的边数
                if(cnt[j]>=n) return true;//假如边数大于等于n，说有环的存在，而且我们是按照01分数规划更新，所有是负环
                if(!st[j])//假如不在队列中则加到队列中
                {
                    q[tt++]=j;
                    st[j]=true;
                }
            }
        }
    }
    return false;//反之没负环
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) cin>>wf[i];
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    double l=0,r=1000;//分析最大可能是1000，最小是0
    while(r-l>1e-4)//二分答案，因为要输出两位小数，则精度得是两位小数，则二分则是多两位是4位
    {
        double mid=(l+r)/2;
        if(spfa(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n",l);
  return 0;
}

3.（单词环）Word Rings

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

这题建图很重要，按照前两个字母与后两个来建图然后前两个字母指向后两个字母边权为该字符串的长度

法一：还有建好图还得spfa假如直接跑就容易wa,这时我们可以加个优化，也就是做题经验，当更新次数超过最大输入的边数的2倍,我们就可以认为是有负环的

法二：还有一种优化方法是把循环队列换成栈，这样更快找到负环

#include<bits/stdc++.h>
using namespace std;
const int N=700,M=1e5+10;
int h[N],e[M],ne[M],w[M],idx;
double dist[N];
int n;
bool st[N];
int cnt[N],q[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(double mid)
{
    memset(st,0,sizeof st);//清空上一层状态
    memset(cnt,0,sizeof cnt);//清空上一层状态
    int hh=0,tt=0;
    int count=0;//用来标记运行的次数
    for(int i=0;i<26*26;i++) q[tt++]=i,st[i]=true;//把所有点入队
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;//循环队列
        st[t]=false;//标记这个点出队了
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+w[i]-mid)//假如满足01分数规划分析的
            {
                dist[j]=dist[t]+w[i]-mid;
                cnt[j]=cnt[t]+1;//更新走的边数
                if(cnt[j]>=N) return true;//假如大于全部的点了，说明有的点已经重复走过了，有环
                if(++count>2*n) return true;//假如运行超过最大边数的两倍也说明有环
                if(!st[j])//假如不在队列中
                {
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
    return false;//则没有环
}
int main()
{
   char str[1010];
   while(scanf("%d",&n),n)
   {
       memset(h,-1,sizeof h);
       idx=0;
       for(int i=0;i<n;i++)
       {
        scanf("%s",str);
         int len=strlen(str);
         if(len<2) continue;
         int a=(str[0]-'a')*26+(str[1]-'a'),b=(str[len-2]-'a')*26+(str[len-1]-'a');//把两个字母对应到26进制中
         add(a,b,len);//把a->b连接起来边权是串的长度
       }
       if(!spfa(0))//假如0都不通过则就是没环了
       {
           puts("No solution");
           continue;
       }
       double l=0,r=1000;
       while(r-l>1e-4)//二分
       {
           double mid=(l+r)/2;
           if(spfa(mid)) l=mid;//假如满足
           else r=mid;
       }
       printf("%lf\n",l);
   }
  return 0;
}

栈优化 

#include<bits/stdc++.h>
using namespace std;
const int N=700,M=1e5+10;
int h[N],e[M],ne[M],w[M],idx;
double dist[N];
int n;
bool st[N];
int cnt[N],q[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(double mid)
{
    memset(st,0,sizeof st);//清空上一层状态
    memset(cnt,0,sizeof cnt);//清空上一层状态
    int tt=0;
    for(int i=0;i<26*26;i++) q[tt++]=i,st[i]=true;//把所有点入队
    while(tt!=0)
    {
        int t=q[--tt];
        st[t]=false;//标记这个点出队了
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+w[i]-mid)//假如满足01分数规划分析的
            {
                dist[j]=dist[t]+w[i]-mid;
                cnt[j]=cnt[t]+1;//更新走的边数
                if(cnt[j]>=N) return true;//假如大于全部的点了，说明有的点已经重复走过了，有环
                if(!st[j])//假如不在队列中
                {
                    q[tt++]=j;
                    st[j]=true;
                }
            }
        }
    }
    return false;//则没有环
}
int main()
{
   char str[1010];
   while(scanf("%d",&n),n)
   {
       memset(h,-1,sizeof h);
       idx=0;
       for(int i=0;i<n;i++)
       {
        scanf("%s",str);
         int len=strlen(str);
         if(len<2) continue;
         int a=(str[0]-'a')*26+(str[1]-'a'),b=(str[len-2]-'a')*26+(str[len-1]-'a');//把两个字母对应到26进制中
         add(a,b,len);//把a->b连接起来边权是串的长度
       }
       if(!spfa(0))//假如0都不通过则就是没环了
       {
           puts("No solution");
           continue;
       }
       double l=0,r=1000;
       while(r-l>1e-4)//二分
       {
           double mid=(l+r)/2;
           if(spfa(mid)) l=mid;//假如满足
           else r=mid;
       }
       printf("%lf\n",l);
   }
  return 0;
}



文章标签：
C++
钊气蓬勃.
目录
相关文章
jianz123
|
SQL 安全 关系型数据库
SQLynx 发布 3.0.0 版本
SQLynx 发布 3.0.0 版本
jianz123
762 1
我不是游客20240119
|
PHP
PHP中的异常处理和错误调试技巧
【8月更文挑战第26天】在编程的世界里，错误和异常是难以避免的。它们像是潜藏在代码深处的小怪兽，时刻准备跳出来给我们制造麻烦。但别担心，我们可以用一些聪明的技巧来驯服这些小怪兽。在这篇文章中，我们将一起学习如何在PHP中找到并解决这些错误和异常。准备好了吗？让我们一起踏上这段充满挑战和乐趣的旅程吧！
我不是游客20240119
114 5
aliyun1645995785-22449
|
资源调度
回归方程优良性评价（原理+实践+代码）
回归方程优良性评价（原理+实践+代码）
aliyun1645995785-22449
286 6
回归方程优良性评价（原理+实践+代码）
xzdrwo43gu6q4
|
存储 消息中间件 监控
APM监控 · 入门篇 · Android端测监控平台建设(2)
微信Matrix框架解析 整体分析
xzdrwo43gu6q4
1206 0
APM监控 · 入门篇 · Android端测监控平台建设(2)
愿荣
|
存储
【DS】树和二叉树的理论知识梳理
【DS】树和二叉树的理论知识梳理
愿荣
330 0
【DS】树和二叉树的理论知识梳理
imzdx
|
缓存 Java
用户登录系统之后，禁止用户返回到登录页面
让页面不缓存，进入页面之后需要重新加载页面：在代码中做判断，在登录页面的路由下，判断用户已登录就跳转首页。   让页面不缓存的方法：JSP   普通页面：
imzdx
1419 0
undefault
|
Linux
DedeCMS后台经常无法加载编辑器
1、编辑器位置 404 无法显示网页 出现404就是路径问题了，也有可能是linux中在目录上是区分大小的哦，这个改一 　　下大小写即可了。 　　解决1：有可能文件出错。重新复制升级包中 “includeFCKeditor”的目录文件 　　解决2：5.5版本只支持fck编辑器,需做如下设置:后台-"系统"-"系统基本参数"-"核心设置"-"Html编辑器选项(目前
undefault
1019 0
tuoxieyz
|
JSON JavaScript 前端开发
淘宝API应用开发小试
无力吐槽淘宝开发平台相关文档的表述清晰度、错误率、各种费解的概念、让人头晕目眩的导航等等。至少能够在几年前就开放众多的API供第三方调用，算得上是有前瞻性的一次重要举措。闲来无事，咱也费心研究了下，有错莫怪我，要怪就怪淘宝文档太不给力。
tuoxieyz
1320 0
LucianaiB
|
12天前
|
人工智能 JSON 机器人
让龙虾成为你的“公众号分身” | 阿里云服务器玩Openclaw
本文带你零成本玩转OpenClaw：学生认证白嫖6个月阿里云服务器，手把手配置飞书机器人、接入免费/高性价比AI模型（NVIDIA/通义），并打造微信公众号“全自动分身”——实时抓热榜、AI选题拆解、一键发布草稿，5分钟完成热点→文章全流程！
LucianaiB
11414 122
让龙虾成为你的“公众号分身” | 阿里云服务器玩Openclaw
$雪地伤孤$
|
2天前
|
人工智能 JSON 监控
Claude Code 源码泄露：一份价值亿元的 AI 工程公开课
我以为顶级 AI 产品的护城河是模型。读完这 51.2 万行泄露的源码，我发现自己错了。
$雪地伤孤$
3204 7