算法提高-图论- 负环

这篇具有很好参考价值的文章主要介绍了算法提高-图论- 负环。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

负环

本博客主要介绍spfa求负环
一般用第二种方法
第一种方法如果每个点入队n次,每次入队也要遍历n次,那么时间复杂度就是n2
第二种方法时间复杂度是n,只要发现最短路边数>=n就说明有环了

算法提高-图论- 负环

AcWing 904. 虫洞

一篇很好的博客,介绍了求负环的常用方法和原理
算法提高-图论- 负环

#include <iostream>
#include <cstring>

const int N = 510, M =2 * 2500 + 200 + 10;

using namespace std;

int dist[N];
int q[N], cnt[N];
bool st[N];
int h[N], ne[M], e[M], w[M], idx;

int T, n, m1, m2;

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

bool spfa()
{
    //memset(dist, 0x3f, sizeof dist);//0x3f也可以ac啊,是因为有负环因为要判断的是负环,
                                      //如果存在负环,那么肯定存在一个点到虚拟源点的距离是负无穷,
                                      //相比于负无穷,0和正无穷都是 一个很大的值,因此这个初始化可以用来更新
    memset(dist, 0, sizeof dist);//这里dist初始化不是0x3f而是0
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    //虚拟源点求负环
    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] + w[i])//这里是求负环,负环对应最短路,因为走负环可以让代价减少所有求的是最短路
            {                            //而正环改变一下符号就行,正环对应最长路,因为走正环可以让代价增加
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (st[j] == false) 
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
                
            }
        }
    }
    return false;
}

int main()
{
    cin >> T;
    while (T -- )
    {
        memset(h, -1, sizeof h);
        idx = 0;
        
        cin >> n >> m1 >> m2;
        for (int i = 0; i < m1; i ++ )
        {
            int a, b ,c;
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
        }
        
        for (int i = 0; i < m2; i ++ )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, -c);//虫洞是单项的而且是负权值
        }
        
        if (spfa()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

AcWing 361. 观光奶牛

这是一个01规划 + 图论问题
算法提高-图论- 负环

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 5000 + 10;

int h[N], wt[M], ne[M], e[M], idx;
int q[N], cnt[N];
int  wf[N];
double dist[N];//dist要变成double!!!
bool st[N];

int n, m;

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

bool check(double mid)
{
    memset(dist, 0, sizeof dist);//这里求的是正环,因此求的是最长路,所以dist初始化为0,这和虫洞那题不一样
    memset(st, 0, sizeof st);//多次check,所以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])//这个是由最初的公式变换来的
            {
                dist[j] = dist[t] + wf[t] - mid * wt[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;//如果mid带入能找到正环,继续找下一个正环,知道找不到正环的时候 此时mid的值才最大
                
                if (st[j] == false)
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
    return false;
}

int main()
{
    cin >> n >> m;    
    for (int i = 1; i <= n; i ++ ) cin >> wf[i];
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    
    double l = 0, r = 1e6;//r是根据我们要的结果在一个什么范围计算出来的(1000 - 1) * 1000,所有干脆取1e6了
    while (r - l > 1e-4)//浮点数二分 + 根据经验值多判断两位的精度
    {
        double mid = (l + r) / 2;// double mid = l + r >> 1 double不能这么写
        if (check(mid)) l = mid;
        else r = mid;
    }
    
    printf("%.2lf", r);//printf("%.2lf", l)也行,因为while退出的时候l == r
}

AcWing 1165. 单词环

判断负环的时候我们可以尝试把我们的队列换成栈,因为栈先进后出,先更新最后进栈的点的邻边,可以更快的找到这个环
算法提高-图论- 负环文章来源地址https://www.toymoban.com/news/detail-500423.html

#include <iostream>
#include <cstring>

const int N = 26 * 26 + 10, M = 1e5 + 10;
int h[N], ne[M], w[M], e[M], idx;
bool st[N];
double dist[N];
int q[N], cnt[N];
int n;

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

// bool check(double mid)
// {
//     memset(st, 0, sizeof st);
//     memset(cnt, 0, sizeof cnt);
    
//     int hh = 0, tt = 0;
//     for (int i = 0; i < 26 * 26; i ++ )//超级源点,把每个点都入队
//     {
//         q[tt ++] = i;
//         st[i] = true;
//     }
//     int count = 0;
//     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)
//             {
//                 dist[j] = dist[t] + w[i] - mid;
//                 cnt[j] = cnt[t] + 1;
//                 if (++ count > 10000) return true;//trick
//                 if (cnt[j] >= N)
//                 if (st[j] == false)
//                 {
//                     q[tt ++ ] = j;
//                     if (tt == N) tt = 0;
//                     st[j] = true;
//                 }
//             }
//         }
//     }
//     return false;
// }

bool check(double mid)
{
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    int hh = 0, tt = 0;
    for (int i = 0; i < 676; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = true;
    }

    int count = 0;
    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)
            {
                dist[j] = dist[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;
                if ( ++ count > 10000) return true; // 经验上的trick
                if (cnt[j] >= 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)
//             {
//                 int left = (str[0] - 'a') * 26 + str[1] - 'a';
//                 int right = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
//                 add(left, right, len);
//             }
//         }

//         if (!check(0)) puts("No solution");
//         else
//         {
//             double l = 0, r = 1000;
//             while (r - l > 1e-4)
//             {
//                 double mid = (l + r) / 2;
//                 if (check(mid)) l = mid;
//                 else r = mid;
//             }

//             printf("%lf\n", r);
//         }
//     }

//     return 0;
// }



int main()
{
    char str[M];
    while(scanf("%d", &n), n)
    {
        idx = 0;//多组数据需要初始化
        memset(h, -1, sizeof h);
        for(int i = 0; i < n; i ++ )
        {
            scanf("%s", &str);//把每个单词的前两个和后两个字符当作一个26进制的数字,这些数字就是一个节点
                              //这样不仅空间复杂度降低了,时间复杂度也降低了,我们通过一个点去遍历它的邻边的时候
                              //这个邻边的另一端一定是和当前节点一样的两个字符,就不用特判了
            int len = strlen(str);
            if (len >= 2)
            {
                int left = (str[0] - 'a') * 26 + (str[1] - 'a');
                int right = (str[len - 2] - 'a') * 26 + (str[len - 1] - 'a');
                add(left, right, len);
            }
        }
        
        if (check(0) == false) puts("No solution");
        else
        {
            double l = 0, r = 1e3;//求的是平均长度,因此二分的答案最多为1000
            while(r - l > 1e-4)//浮点数二分
            {
                double mid = (l + r) / 2; 
                if (check(mid)) l = mid;//都说错了,这是浮点数二分,不用管着么多xxxxmid满足了,那么答案肯定不取mid了,左边界更新为mid + 1;
                else r = mid;               
            }
            printf("%.2lf\n", r);
        }
    }
    return 0;
}

到了这里,关于算法提高-图论- 负环的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法模板(3):搜索(3):图论提高

    (1)朴素版prim算法( O ( n 2 ) O(n ^ 2) O ( n 2 ) ) 适用范围:稠密图 易错:注意有向图还是无向图;注意有没有重边和负权边。 从一个集合向外一个一个扩展,最开始只有 1 1 1 这个结点,然后把元素一个一个加进来,每次加的元素就是离这个集合距离最小的元素,可以设为

    2024年02月09日
    浏览(42)
  • 算法提高-图论-单源最短路的扩展应用

    多源点单终点最短路建图: 创建虚拟源点(创建虚拟源点的时候以是spfa为例 可以在建图的时候建出来,也可以在spfa这直接入队,也是虚拟源点的意思) 反向建图变成单源点多终点,然后遍历终点的dist即可找出最短路 这题挺简单的就不详细说了,主要是第一次遇到计数问题

    2024年02月16日
    浏览(47)
  • 算法提高-图论-单源最短路的综合应用

    多次dijkstra求每个点到其它点的最短距离, 此时相当于建好了一张图,每个点之间的最短距离都知道了,接下来dfs搜一下怎么走最短即可 一篇博客解释了为什么一个正向建图求最小值,反向建图求最大值 根本思想是保证1到n的买卖是连通的

    2024年02月11日
    浏览(60)
  • 算法提高-图论-单源最短路的建图方式

    建图 找出一个牧场,它到其他牧场的距离之和最小 我是这么理解的,djsktra是一个贪心的思想,加法里面不能加负数我就不说了 求乘法最大值的时候为什么边权必须0-1,因为在乘法最大值里面有一个边权大于1的话那不就等价于求加法最小值的时候有一个边权为负数的么,d

    2024年02月08日
    浏览(44)
  • 第三章 图论 No.6负环之01分数规划与特殊建图方式

    裸题:904. 虫洞 904. 虫洞 - AcWing题库 这个==真的服,调半天,还有,邻接表的大小又设置错了 01分数规划:361. 观光奶牛 361. 观光奶牛 - AcWing题库 在图论问题中,所有形如:某个部分之和除以某个部分之和最大的问题,被称为01分数规划,通常使用二分解决这类问题 根据题意

    2024年02月13日
    浏览(41)
  • acwing算法提高之图论--最小生成树的扩展应用

    本专题用来记录使用最小生成树算法(prim或kruskal)解决的扩展题目。 题目1 :1146新的开始 C++代码如下, 题目2 :1145北极通讯网络 C++代码如下, 题目3 :346走廊泼水节 C++代码如下, 题目4 :1148秘密的牛奶运输 C++代码如下,

    2024年04月16日
    浏览(36)
  • acwing算法提高之图论--最小生成树的典型应用

    本专题用来记录使用prim算法或kruskal算法求解的题目。 题目1 :1140最短网络 C++代码如下, 题目2 :1141局域网 C++代码如下, 题目3 :1142繁忙的都市 C++代码如下, 题目4 :1143联络员 C++代码如下, 题目5 :1144连接格点 C++代码如下,

    2024年04月27日
    浏览(39)
  • 详细介绍MATLAB中的图论算法

    MATLAB是一种功能强大的编程语言和环境,提供了许多用于图论算法的工具和函数。图论是研究图及其属性和关系的数学分支,广泛应用于计算机科学、网络分析、社交网络分析等领域。在MATLAB中,我们可以使用图论算法来解决各种问题,如最短路径问题、最小生成树问题、最

    2024年02月16日
    浏览(48)
  • bellman_ford算法判负环-洛谷P3371

    总结:这题改了很久,一直wa 问题一:多测要清空数组 问题二:本题其实有点特殊,它要求的是,从1开始出发能到达的负环,也就是这个1实际上必须能到这个负环,如果图不连通,就会出现有负环但1去不了,等于没有负环的情况,这种特殊情况bellman_ford算法是压根没法解决的 一个玄学方法

    2024年02月06日
    浏览(34)
  • 第十八章 SPFA算法以及负环问题(利用dijkstra推导出该算法,超级详细!!)

    我们回顾一下之前的dijkstra算法的证明过程。如果大家没看过之前的dijkstra算法的简易证明的话,作者在这里建议先去看一下。 传送门: 第十六章 Dijkstra算法的讲解以及证明(与众不同的通俗证明) 那么假设你已经看过这篇文章,我们发现,我们将每次松弛操作后的最小距离

    2024年02月02日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包