circle

【from new_dtoj 3971: circle】
题目描述
小w 的男朋友送给小w 一个n个点m条边的图，并且刁难小w 要她找出点数最少的正环。
小w 不会做，于是向你求助。
输入
第一行两个整数n,m。
接下来m行，每行四个数u,v,a,b，表示从u走到v的代价为a，从v走到u的代价为b（算作两条不同的边）。注意a,b可能为负。
输出
当图中包含正环时，输出点数最少的正环（简单环）的点数。
否则输出0。
样例输入
3 3
1 2 2 -1
2 3 10 -10
3 1 10 -10
样例输出
2
提示
对于前20%的数据，n≤7,m≤10。
对于前60%的数据，n≤150,m≤2000。
对于100%的数据，1≤n≤300,0≤m≤n(n−1)2,|a|,|b|≤$10^4$。
数据保证不存在重边和自环。
题解：
考虑dp
设$F_{i,j,k}$表示从$j$走到$k$用了$2^k$步
转移：$F_{i,j,k}=max(F_{i-1,j,l}+F_{i-1,l,k})$
接着我们可以二分步数，再开一个数组$s_{i,j}$表示在这个步数下的$i$到$j$的最长路，只需要枚举$i$看$i$到$i$的最长路是否大于$0$
具体见代码

#include <cstdio>
#include <string>
#define _(d) while(d(isdigit(c=getchar())))
#define I inline
using namespace std;
I int R(){
    int x,f=1;char c;_(!)c=='-'?f=0:f;x=(c^48);
    _()x=(x<<3)+(x<<1)+(c^48);return f?x:-x;
}
const int N=305;
int l=2,r,p,n,m,d[10][N][N],s[2][N][N];
I bool J(){
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[0][i][j]=i==j?0:-1e9;
    int ty=0;for (int k=0;(1<<k)<=p;k++)
        if (p&(1<<k)){
            ty^=1;for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[ty][i][j]=i==j?0:-1e9;
            for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)
            for (int l=1;l<=n;l++)
                if (s[ty^1][i][l]+d[k][l][j]>s[ty][i][j])
                    s[ty][i][j]=s[ty^1][i][l]+d[k][l][j];
        }
    for (int i=1;i<=n;i++) if (s[ty][i][i]>0) return 1;return 0;
}
int main(){
    n=R();m=R();r=n+1;
    for (int k=0;(1<<k)<=n;k++) for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++) d[k][i][j]=i==j?0:-1e9;
    for (int u,v,x,y,i=1;i<=m;i++){
        u=R(),v=R(),x=R(),y=R();
        if (d[0][u][v]<x) d[0][u][v]=x;
        if (d[0][v][u]<y) d[0][v][u]=y;
    }
    for (int k=1;(1<<k)<=n;k++) for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++) for (int l=1;l<=n;l++)
        if (d[k-1][i][l]+d[k-1][l][j]>d[k][i][j])
            d[k][i][j]=d[k-1][i][l]+d[k-1][l][j];
    while(l<r){p=l+r>>1;if (J()) r=p;else l=p+1;}
    if (l==n+1) l=0;return printf("%d
",l),0;
}