Smile House_牛客博客

题意

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

分析

考虑 $dp$ 转移式，设 $dp[s][i][j]$ 表示走了不超过 $2^s$ 条边，从 $i$ 到 $j$ 的最大边权(走不通为极小值)。
那么转移为： $dp[s][i][j]=max(dp[s-1][i][k]+dp[s-1][k][j])$

在我们计算答案时，我们考虑使用倍增。
先尝试走了不超过 $2^s$ 条边从 $x$ 走到了 $y$ 的最小边权和, $s$ 从大到小枚举。
1.如果没有正环，说明答案大于 $2^s$ ,那么下一步增加 $2^{s-1}$ 条边。
转移时需用到上一次状态，用 $now[i][j]$ 记录上一次尝试 $i \to j$ 的最长路径。
2.如果有正环，说明答案小于等于 $2^s$ ，那么下一步尝试 $2^{s-1}$ 条边。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=300+5,M=10,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m,x,y,z,w,ans;
int dp[M+5][N][N];
int tmp[N][N] ,now[N][N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

int main()
{
    memset(now,0xcf,sizeof(now));
    memset(dp,0xcf,sizeof(dp));
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read(),w=read();
        dp[0][x][y]=z;dp[0][y][x]=w;
    }
    for(int i=1;i<=n;i++)
        now[i][i]=0,dp[0][i][i]=0;
    for(int s=1;s<=M;s++)
     for(int k=1;k<=n;k++)
      for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
        dp[s][i][j]=max(dp[s][i][j],dp[s-1][i][k]+dp[s-1][k][j]);
    for(int s=M;s>=0;s--) 
    {
        memset(tmp,0xcf,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],now[i][k]+dp[s][k][j]);
        bool f=0;
        for(int i=1;i<=n;i++)
         if(tmp[i][i]>0) 
          {f=1;break;}
        if(f) continue;
        else
        {
            for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
              now[i][j]=tmp[i][j];
            ans+=1<<s;
        }
    }
    printf("%d",ans>=n?0:ans+1);
    return 0;
}