负环 BZOJ 4773

负环

【问题描述】

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

【输入格式】

第1两个整数n, m,表示图的点数和边数。

接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。

【输出格式】

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

【样例输入】

3 6
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10

【样例输出】

【数据范围】

2 <= n <= 300, 0 <= m <= n(n <= 1), 1 <= ui, vi <= n, |wi| <= 10^4

题解：

考虑二分最小点数，用 Floyed （用倍增来限制步数）检验答案的范围区间

那么将二分过程化为倍增的过程，可行时不断缩小答案，否则继承当前答案

 #include<cmath>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 const int logn = ;

 inline int Get()

 {

     int x;

     char c;

     bool o = false;

     while((c = getchar()) < '' || c > '')

         if(c == '-') o = true;

     x = c - '';

     while((c = getchar()) >= '' && c <= '')

         x = x *  + c - '';

     return (o) ? -x : x;

 }

 int n, m;

 int f[maxn][maxn][logn + ], g[maxn][maxn], s[maxn][maxn];

 inline void Clear()

 {

     memset(f,  / , sizeof(f));

     for(int k = ; k <= logn; ++k)

         for(int i = ; i <= n; ++i)

             f[i][i][k] = ;

     memset(s,  / , sizeof(s));

     for(int i = ; i <= n; ++i) s[i][i] = ;

 }

 int main()

 {

     n = Get(), m = Get();

     Clear();

     for(int i = ; i <= m; ++i)

     {

         int x = Get(), y = Get(), z = Get();

         f[x][y][] = z;

     }

     for(int l = ; l <= logn; ++l)

         for(int i = ; i <= n; ++i)

             for(int j = ; j <= n; ++j)

                 for(int k = ; k <= n; ++k)

                     f[i][j][l] = min(f[i][j][l], f[i][k][l - ] + f[k][j][l - ]);

     int ans = ;

     for(int l = logn; l >= ; --l)

     {

         memcpy(g, s, sizeof(g));

         for(int i = ; i <= n; ++i)

             for(int j = ; j <= n; ++j)

                 for(int k = ; k <= n; ++k)

                     s[i][j] = min(s[i][j], g[i][k] + f[k][j][l]);

         bool flag = false;

         for(int i = ; i <= n; ++i)

             if(s[i][i] < )

             {

                 flag = true;

                 break;

             }

         if(flag) memcpy(s, g, sizeof(s));

         else ans += ( << l);

     }

     if(ans > n) printf("0\n");

     else printf("%d\n", ans);

 }

巴特西

负环 BZOJ 4773

最新文章

热门文章