欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj4773 负环

程序员文章站 2022-05-22 15:20:19
...

Description
在忘记考虑负环之后,黎瑟的算法又出错了。对于边带权的有向图 G = (V, E),请找出一个点数最小的环,使得
环上的边权和为负数。保证图中不包含重边和自环。

Input
第1两个整数n, m,表示图的点数和边数。
接下来的m行,每<=三个整数ui, vi, wi,表<=有一条从ui到vi,权值为wi的有向边。
2 <= n <= 300
0 <= m <= n(n <= 1)
1 <= ui, vi <= n
|wi| <= 10^4

Output
仅一行一个整数,表示点数最小的环上的点数,若图中不存在负环输出0。

Sample Input
3 6
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10

Sample Output
2

分析:
求负环:
A:bellmax ford
B:floyed
C:spfa(扔下去。。。)

设计状态
f[k][i][j]表示i到j经过k个点的最短路
枚举k和i,
如果存在f[k][i][i]是负数, 那么就是一个负环
k可以通过倍增得到:f[k]<—f[k-1],f[k-1]
这只是基本原理
具体实现有一些细节

其实我们需要进行两次floyed
第一次利用倍增的方法
维护好f[k][i][j]
f[k][i][j]=min(f[k-1][i][l]+f[k-1][l][j]);

但是这样的话我们只知道走2^k步时的答案
想想第一次接触倍增是什么时候
没错,LCA
那时候我们是怎么处理的呢
for (i=lg;i>=0;i–)
这就相当于把答案二进制分解了
得出的答案+1就是最终答案

这道题也是一样

我们要求的是不存在负环的最大步数,

最大步数+1即为答案

第一次floyed我们得到了一个k(走2^k出现负环)
那答案一定<=2^k
我们就把k从大到小循环
只要是f[k][i][i]>0
ans+=(1 << k)

当然还有一些细节要处理
还记得我们一开始记录了一个h邻接矩阵
在循环的开始
我们先调用一个全新的函数:memecpy(a,b,sizeof(b))
表示b中的信息全部复制到a

这个while循环我们可以一步一步看
首先memcpy,g保存一下h数组的信息
设g记录了走x步时的floyed的答案
之后就进行了一次耳熟能详的floyed
用来判断在走2^k+x步数的情况下
能不能走出负环,

能:把h数组的信息还原(这个2^k+x太大了,不符合我们找最大非负环的限制)

不能:ans+=(1 << k),h数组中的信息保留(走2^k+x)

这个h/g数组就相当于记录没有负环的最大步数

ans记录走了多少步

最后输出ans+1

tip

变量名不要搞错了

这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

const int N=310;
const int lg=10;
int n,m,f[lg][N][N],g[N][N],h[N][N],ans;

void floyed()
{
    int i,j,k,l;
    for (k=1;k<lg;k++)
    {
        bool ff=0;
        for (l=1;l<=n;l++)  //最外层循环折点 
            for (i=1;i<=n;i++)
                for (j=1;j<=n;j++)
                {
                    f[k][i][j]=min(f[k][i][j],f[k-1][i][l]+f[k-1][l][j]);
                }
        for (i=1;i<=n;i++)
            if (f[k][i][i]<0) ff=1;
        if (ff) break;
        if ((1<<k)>=n)  //整张图都不存在负环 
        {
            puts("0");
            return;
        }
    }
    ans=0;
    while (k>=0)  //步数
    {
        memcpy(g,h,sizeof(h));
        bool ff=0;
        for (l=1;l<=n;l++)
            for (i=1;i<=n;i++)
                for (j=1;j<=n;j++)
                    h[i][j]=min(h[i][j],g[i][l]+f[k][l][j]);
        for (i=1;i<=n;i++)
            if (h[i][i]<0) ff=1;
        if (ff) memcpy(h,g,sizeof(g));  //恢复信息 
        else ans+=(1<<k);
        k--;
    } 
    printf("%d",ans+1);
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(f,0x33,sizeof(f));
    memset(h,0x33,sizeof(h));
    for (int i=1;i<=n;i++) f[0][i][i]=h[i][i]=0;   //h邻接矩阵 
    for (int i=1;i<=m;i++) 
    {
        int u,w,z;
        scanf("%d%d%d",&u,&w,&z);
        f[0][u][w]=z;
    }
    floyed();
    return 0;
}
相关标签: 最短路