题目链接：http://codeforces.com/contest/147/problem/B
求有向图的最小正权环的大小 ${n<=300}$
非常显然的有${n^{3}log^2}$的做法，令${f_{(s,i,j)}}$表示从第${i}$个点走到第${j}$个点走了${2^{s}}$步的最大权值，然后二分答案，每次利用$f$数组计算答案。
问题在于算一下时间感觉是不太对的...然而居然跑过去了 QwQ
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 310
#define llg int
#define inf 0x3f3f3f3f
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,a[][maxn][maxn],dp[][maxn][maxn],up; inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
} void init()
{
cin>>n>>m;
up=(llg)floor(log2((long double)n));
for (llg i=;i<=up;i++) for (llg j=;j<=n;j++) for (llg k=;k<=n;k++) dp[i][j][k]=-*inf;
for (llg s=;s<=up;s++) for (llg i=;i<=n;i++) dp[s][i][i]=;
for (llg i=;i<=m;i++)
{
llg u=getint(),v=getint();
dp[][u][v]=getint(),dp[][v][u]=getint();
}
} void make_dp()
{
for (llg s=;s<=up;s++)
for (llg k=;k<=n;k++)
for (llg i=;i<=n;i++)
{
if(dp[s - ][i][k]==-inf) continue;
for (llg j=;j<=n;j++)
dp[s][i][j]=max(dp[s][i][j],dp[s-][i][k]+dp[s-][k][j]);
}
} bool check(llg x)
{
for (llg i=;i<=up;i++) for (llg j=;j<=n;j++) for (llg k=;k<=n;k++) a[i][j][k]=-*inf;
for (llg i=;i<=n;i++) a[][i][i]=;
llg p=;
for (llg s=;s<=up;s++)
{
if (((x>>s)&)==) continue;
p++;
for (llg i=;i<=n;i++) a[p][i][i]=;
for (llg k=;k<=n;k++)
for (llg i=;i<=n;i++)
for (llg j=;j<=n;j++)
a[p][i][j]=max(a[p][i][j],a[p-][i][k]+dp[s][k][j]);
}
for (llg i=;i<=n;i++) if (a[p][i][i]>) return ;
return ;
} int main()
{
yyj("a");
init();
make_dp();
llg l=,r=n+,ans=;
while (l<=r)
{
llg mid=(l+r)>>;
if (check(mid)) r=mid-,ans=mid;else l=mid+;
}
if (l>=n+) ans=;
cout<<ans;
return ;
}