题意翻译

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

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

输入格式

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

接下来行，一行四个整数，表示到有一条边，到的边权为，到的边权为

输出格式

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

如果没有正环请输出

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

数据范围与约定

对于的数据，保证;

对于的数据，保证;

对于的数据，保证;

分析

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

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

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

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

其中，均需要在转移时枚举，时间复杂度为，无法通过的数据。但您可以拿到80分

考虑如何优化这个。由于这个基于，因此必须进行枚举，而却可以使用倍增来优化。

则我们重新设计状态。设表示从到经过条边的路径大小，可得状态转移方程$$

这个过程的时间复杂度是的。

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

若不存在正环(即)，则证明答案大于。下一次转移时增加条边即可。

否则的话证明答案小等于，下一次转移时仅尝试条边即可。

时间复杂度为，足以通过本题。

剩下的见代码注释。

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