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

bzoj4773: 负环

程序员文章站 2022-05-22 15:04:52
...

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

题解

又长新姿势了,lalal
这题想了很久,只想到一个dfs,然而虽然看起来挺好,但实际上跑不过,我试过了TAT

然后羊老师教我秒题。。

新姿势:跑多次floyd找负环Get
具体看代码吧,应该看得懂

顺便学了一下倍增floyd,但是这题我没打。。其实可以二分答案+倍增floyd,就可以n3(log2n)了。。但是对于300似乎差得也不是特别多。。

#include<cstdio>
#include<cstring>
const int N=305;
int n,m;
int f[N][N];
int g[N][N];
int a[N][N];
int mymin (int x,int y){return x<y?x:y;}
int main()
{
    scanf("%d%d",&n,&m);
    for (int u=1;u<=n;u++)
        for (int i=1;i<=n;i++)
            a[u][i]=f[u][i]=g[u][i]=(1<<28);
    for (int u=1;u<=m;u++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        f[x][y]=mymin(f[x][y],z);
        g[x][y]=mymin(g[x][y],z);
    }
    bool tf=false;
    for (int u=1;u<=n;u++)
    {
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    a[j][k]=mymin(f[j][i]+g[i][k],a[j][k]);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                f[i][j]=a[i][j];
        for (int i=1;i<=n;i++)
            if (f[i][i]<0)
                {
                    tf=true;
                    break;
                }
        if (tf) 
        {
            printf("%d\n",u+1);
            break;
        }
    }
    if (tf==false) printf("0\n");
    return 0;
}