题目描述

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

题目分析

据说这叫倍增floyd
表示从出发经过条边到的最短路
先预处理出这个
然后利用倍增lca的思想 从高到低枚举lg 先和跑一边floyd 如果没有负环就更新答案
最后的结果无限逼近答案 +1就好了

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int f[10][310][310],lg,ans;
int h[310][310],g[310][310];
int main()
{   
    scanf("%d%d",&n,&m);
    memset(h,0x33,sizeof h);
    memset(f,0x33,sizeof f);
    for(int i=1;i<=n;i++) f[0][i][i]=h[i][i]=0;
    for(int x,y,c,i=1;i<=m;i++)
        scanf("%d%d%d",&x,&y,&c),f[0][x][y]=c;
    int flag=0;
    for(lg=1;lg<=9;lg++)
    {
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    f[lg][i][j]=min(f[lg][i][j],f[lg-1][i][k]+f[lg-1][k][j]);
        for(int i=1;i<=n;i++)
            if(f[lg][i][i]<0) flag=1;
        if(flag) break;
        if(1<<(lg)>=n) { printf("0"); return 0; }
    }
    for(;lg>=0;lg--)
    {
        memcpy(g,h,sizeof h);
        flag=0;
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    h[i][j]=min(h[i][j],g[i][k]+f[lg][k][j]);
        for(int i=1;i<=n;i++) if(h[i][i]<0) flag=1;
        if(flag) memcpy(h,g,sizeof g);
        else ans+=(1<<lg); 
    }
    printf("%d",ans+1);
    return 0;   
}