做法：floyd+倍增

题意：

  • 求最小正环的大小

思路：

  1. 利用floyd+倍增的方法跑最长路
  2. 路径数量从大到小的方法来判断是否成立（类似二分的思想）
    1）若存在正环，则，则答案不需要增加
    2）若不存在正环，则，则答案需要增加，并且更新f数组

代码

// Problem: Smile House
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/109328
// Memory Limit: 524288 MB
// Time Limit: 6000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=310;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m,ans=1;
int d[10][N][N]; //d[s][i][j]:走了不超过2^s条边，从i到j的最大边权
int f[N][N],tmp[N][N];
int lg[N];
void init(){
    for(int i=1;i<=n;i++){
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    mst(d,-INF);mst(f,-INF);
    for(int i=1;i<=n;i++){
        d[0][i][i]=0;f[i][i]=0;
    }
}

void floyd(){
    for(int s=1;s<=lg[n];s++){
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    d[s][i][j]=max(d[s][i][j],d[s-1][i][k]+d[s-1][k][j]);
                }
            }
        }
    }
}

void solve(){
    cin>>n>>m;
    init();
    while(m--){
        int u,v;cin>>u>>v;
        cin>>d[0][u][v]>>d[0][v][u];
    }
    floyd();
    for(int s=1;s<=lg[n];s++){
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    d[s][i][j]=max(d[s][i][j],d[s-1][i][k]+d[s-1][k][j]);
                }
            }
        }
    }

    for(int s=lg[n];~s;s--){
        mst(tmp,-INF);
        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],f[i][k]+d[s][k][j]);
                }
            }
        }
        bool flag=0;
        for(int i=1;i<=n;i++){
            if(tmp[i][i]>0){
                 flag=1;
                 break;
            }
        }
        if(flag) continue;//有正环
        else{
            ans+=(1<<s);
            memcpy(f,tmp,sizeof tmp);
        }
    }
    if(ans>n) cout<<"0\n";
    else cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}