Codeforces 147 B. Smile House

题目链接：http://codeforces.com/contest/147/problem/B

求有向图的最小正权环的大小 ${n<=300}$

非常显然的有${n^{3}log^2}$的做法，令${f_{(s,i,j)}}$表示从第${i}$个点走到第${j}$个点走了${2^{s}}$步的最大权值，然后二分答案，每次利用$f$数组计算答案。

问题在于算一下时间感觉是不太对的...然而居然跑过去了 QwQ

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<cstring>
 8 using namespace std;
 9 #define maxn 310
10 #define llg int
11 #define inf 0x3f3f3f3f
12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
13 llg n,m,a[21][maxn][maxn],dp[21][maxn][maxn],up;
14 
15 inline int getint()
16 {
17     int w=0,q=0; char c=getchar();
18     while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
19     while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
20 }
21 
22 void init()
23 {
24     cin>>n>>m;
25     up=(llg)floor(log2((long double)n));
26     for (llg i=0;i<=up;i++) for (llg j=1;j<=n;j++) for (llg k=1;k<=n;k++) dp[i][j][k]=-1*inf;
27     for (llg s=0;s<=up;s++)  for (llg i=1;i<=n;i++) dp[s][i][i]=0;
28     for (llg i=1;i<=m;i++)
29     {
30         llg u=getint(),v=getint();
31         dp[0][u][v]=getint(),dp[0][v][u]=getint();
32     }
33 }
34 
35 void make_dp()
36 {
37     for (llg s=1;s<=up;s++)
38         for (llg k=1;k<=n;k++)
39             for (llg i=1;i<=n;i++)
40             {
41                  if(dp[s - 1][i][k]==-inf) continue;
42                 for (llg j=1;j<=n;j++) 
43                     dp[s][i][j]=max(dp[s][i][j],dp[s-1][i][k]+dp[s-1][k][j]);
44             }
45 }
46 
47 bool check(llg x)
48 {
49     for (llg i=0;i<=up;i++) for (llg j=1;j<=n;j++) for (llg k=1;k<=n;k++) a[i][j][k]=-1*inf;
50     for (llg i=1;i<=n;i++) a[0][i][i]=0;
51     llg p=0;
52     for (llg s=0;s<=up;s++)
53     {
54         if (((x>>s)&1)==0) continue;
55         p++;
56         for (llg i=1;i<=n;i++) a[p][i][i]=0;
57         for (llg k=1;k<=n;k++)
58             for (llg i=1;i<=n;i++)
59                 for (llg j=1;j<=n;j++)
60                     a[p][i][j]=max(a[p][i][j],a[p-1][i][k]+dp[s][k][j]);
61     }
62     for (llg i=1;i<=n;i++) if (a[p][i][i]>0) return 1;
63     return 0;
64 }
65 
66 int main()
67 {
68     yyj("a");
69     init();
70     make_dp();
71     llg l=2,r=n+1,ans=0;
72     while (l<=r)
73     {
74         llg mid=(l+r)>>1;
75         if (check(mid)) r=mid-1,ans=mid;else l=mid+1;
76     }
77     if (l>=n+1) ans=0;
78     cout<<ans;
79     return 0;
80 }