题意翻译

给你$n$个点，$m$条边的无向图。但一条无向边的两个方向的边权不同，求图上最小正环的大小。

正环为从一个点出发再回到这个点经过所有边边权之和为正，定义最小正环的含义为这个正环经过的点数最少

输入格式

第一行两个整数$n$，$m$，表示点数和边数

接下来$m$行，一行四个整数$x,y,z,w$，表示$x$到$y$有一条边，$x$到$y$的边权为$z$，$y$到$x$的边权为$w$

输出格式

输出仅有一行，包含一个整数，表示最小正环的大小（即这个正环上点的个数）。

如果没有正环请输出$0$

Input & Output ‘s examples

Input ‘s eg

4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3

Output ‘s eg

4

数据范围与约定

对于$30\%$的数据，保证$n<=10$;

对于$60\%$的数据，保证$n<=100$;

对于$100\%$的数据，保证$n<=300$;

分析

一道看起来很像搜索的动态规划。(考场上爆搜打挂的我哭出声来)

不难看出，这题是在图上做的，且这题的数据范围极小。很容易就能想到$Floyd$。

而$Floyd$的本质是$DP$。考虑如何在$Floyd$的基础上$DP$。

设$f[l][i][j]$表示从$i$到$j$经过$l$条边的路径大小，可得状态转移方程

其中，$l,i,j,k$均需要在转移时枚举，时间复杂度为$O(n^4)$，无法通过$100\%$的数据。但您可以拿到80分

考虑如何优化这个$DP$。由于这个$DP$基于$Floyd$，因此$i , j , k$必须进行枚举，而$l$却可以使用倍增来优化。

则我们重新设计状态。设$f[l][i][j]$表示从$i$到$j$经过$2^l$条边的路径大小，可得状态转移方程

这个过程的时间复杂度是$O(n^3 \log n)$的。

之后我们采用类似于倍增爬树的方法来求解答案。首先，我们先尝试走$2^l$条边从$i$到$j$的路径大小。

若不存在正环(即$f[l][i][i] < 0$)，则证明答案大于$2^l$。下一次转移时增加$2^{l - 1}$条边即可。

否则的话证明答案小等于$2^l$，下一次转移时仅尝试$2^{l - 1}$条边即可。

时间复杂度为$O(n^3 \log n)$，足以通过本题。

剩下的见代码注释。

Code[80pts]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 301

using namespace std;

int n , m;
int f[N][N][N];


int main(){
    cin >> n >> m;
    int u , v , d1 , d2;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){       //初始化数组
            for(int k = 1; k <= n; k ++){
                f[i][j][k] = -0x3f3f3f3f;
            }
        }
    }
    for(int i = 1; i <= m; i ++){
        cin >> u >> v >> d1 >> d2;
        f[1][u][v] = d1;
        f[1][v][u] = d2;
    }
    for(int l = 2; l <= n; l ++){
        for(int k = 1; k <= n; k ++){
            for(int i = 1; i <= n; i ++){
                for(int j = 1; j <= n; j ++){
                    f[l][i][j] = max(f[l][i][j] , f[l - 1][i][k] + f[1][k][j]);
                }
                if(f[l][i][i] > 0){ //如果找到了一个正环，则输出环的长度即可。
                    cout << l << "\n";
                    return 0;
                }
            }
        }
    }
    puts("0");
    return 0;
}

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 301

using namespace std;

int n, m, ans;
int u , v , d1 , d2;
int f[15][N][N];
int tmp[N][N], last[N][N];

int main(){
    memset(last, -0x3f3f3f3f, sizeof(last));
    memset(f, -0x3f3f3f3f, sizeof(f));

    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> u >> v >> d1 >> d2;
        f[0][u][v] = d1;
        f[0][v][u] = d2;
    }
    for (int i = 1; i <= n; i++){
        last[i][i] = 0;
        f[0][i][i] = 0;
    }

    for (int l = 1; l <= 10; l++){
        for (int k = 1; k <= n; k++){
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n; j++){
                    f[l][i][j] = max(f[l][i][j], f[l - 1][i][k] + f[l - 1][k][j]);
                }
            }
        }
    } 
    for (int l = 10; l >= 0; l--){
        memset(tmp, -0x3f3f3f3f, sizeof(tmp));

        for (int k = 1; k <= n; k++){
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n; j++){
                    tmp[i][j] = max(tmp[i][j], last[i][k] + f[l][k][j]);
                }
            } 
        }

        bool flag = false;
        for (int i = 1; i <= n; i++){
            if (tmp[i][i] > 0){
                flag = true;
                break;
            }
        }

        if (flag) continue; 
        else{ 
            for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n; j++){
                    last[i][j] = tmp[i][j];
                }  
            }
                
            ans += 1 << l;
        }
    }
    cout << (ans >= n ? 0 : ans + 1) << "\n";
    return 0;
}

THE END