CodeForces

Luogu

分析

很神仙的题目。

重新定义矩阵的乘法运算:设 $C=A\times B$ ,那么 $C_{i,j}=\max\left\{A_{i,j},B_{i,j},A_{i,k}+B_{k,j}\right\}$ 。

定义矩阵 $A^t$ ,其元素 $(i,j)$ 表示走不超过 $2^t$ 步从 $i$ 到 $j$ 的最大边权和。

那么显然有 $A^t=A^{t-1}\times A^{t-1}$ 。

现在来算答案。枚举每个二进制位 $t$ ,如果继续走 $2^t$ 步还不能出现一个正环,就把答案加上 $2^t$ 。

最后如果答案 $>n$ 了就输出 $0$ ,否则加上 $1$ 再输出。

可能讲的不是很清楚,建议结合代码+模拟+画图理解qwq

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

template<typename T>
inline void chkmax(T& x,T y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300+10;
const int T=9;

int n,m;

struct Matrix {
    int s[N][N];
    int* operator[](int i) { return s[i]; }
    inline void init() { memset(s,0xc0,sizeof(s)); }
} A[T+5],now,nxt;

Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            c[i][j]=max(a[i][j],b[i][j]);
            for (re int k=1;k<=n;++k) chkmax(c[i][j],a[i][k]+b[k][j]);
        }
    return c;
}

int main() {
    n=read(),m=read(); now.init(),A[0].init();
    for (re int i=1;i<=n;++i) now[i][i]=0;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        A[0][u][v]=read(),A[0][v][u]=read();
    }
    for (re int i=1;i<=T;++i) A[i]=A[i-1]*A[i-1];
    int ans=0;
    for (re int i=T;~i;--i) {
        nxt=now*A[i]; int flag=0;
        for (re int j=1;j<=n;++j)
            if (nxt[j][j]>0) { flag=1; break; }
        if (flag) continue;
        now=nxt,ans+=(1<<i);
    }
    if (ans>n) puts("0");
    else printf("%d\n",ans+1);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 11 PM