Description

给定一个带权有向图，边权可能为负，输出边数最小的正环，并保证边数最小的情况下使环内边权和最大，输出最大边权和。 2<=N<=300,2<=M<=N*(N-1)

Analysis

并不知道SPFA能不能做，好像是水法 弄一个邻接矩阵 Ak[N][N] ，我们可以像矩阵乘法一样乘法若干次，求出某点走若干步到某点的最长路，那么 Ak 就表示乘了k次 于是，朴素想法可以乘一次判断一次，但是乘法为O(n^3)的，总复杂度为O(n^4) TLE 一次一次乘太慢了，我们可以采用倍增的思想 Ak 改成表示乘 2k 后的结果 一直乘，直到满足条件的前一个k 然后，可以以A的2的幂相乘得到最后的答案，k从大到小，倍增的思想只要不合法就乘 时间复杂度优化为 O(n3logn) 注意，本题需要一定卡常技巧

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; const int N=305; typedef ll mat[N][N]; int _2[N],n,m; mat a,b,c[N]; ll pd(mat a) { ll mx=0; fo(i,1,n) mx=max(mx,a[i][i]); return mx; } void mul(mat &c,mat a) { memset(c,0,sizeof(c)); } int main() { freopen("utrka.in","r",stdin); freopen("utrka.out","w",stdout); _2[0]=1; fo(i,1,20) _2[i]=_2[i-1]*2; int u,v,x,y; scanf("%d %d",&n,&m); memset(c,200,sizeof(c)); fo(i,1,m) { scanf("%d %d %d %d",&u,&v,&x,&y); c[0][u][v]=y-x; } int l=1; for(;;l++) { memcpy(c[l],c[l-1],sizeof(c[l-1])); fo(i,1,n) fo(j,1,n) fo(k,1,n) c[l][i][j]=max(c[l][i][j],c[l-1][i][k]+c[l-1][k][j]); if(pd(c[l])) break; } l--; memcpy(a,c[l],sizeof(c[l])); int ans=_2[l]; while(--l>=0) { memcpy(b,a,sizeof(a)); fo(i,1,n) fo(j,1,n) fo(k,1,n) b[i][j]=max(b[i][j],a[i][k]+c[l][k][j]); if(!pd(b)) { memcpy(a,b,sizeof(b)); ans+=_2[l]; } } printf("%d ",ans+1); memcpy(b,a,sizeof(a)); fo(i,1,n) fo(j,1,n) fo(k,1,n) b[i][j]=max(b[i][j],a[i][k]+c[0][k][j]); printf("%d",pd(b)); return 0; }