[JZOJ3640] 【COCI2014】utrka

Description

2<=N<=300,2<=M<=N*(N-1)

Solution

就是对于整个有向图，求边数最少的正环并且环上长度和要尽可能的大。

N<=300 可以矩阵乘法。 邻接矩阵乘K次就是走了K步。

那么可以用类似倍增LCA的做法 走 1,2,22,23,24... 找到在哪两个之间然后Log 逼近 Log M找到最小的一个满足条件的K。 注意常数优化。 矩乘 N3 总的复杂度 O(N3logM)

Code

#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) #define INF 1000000000 #define LL long long #define N 305 int n,m,s1,s2; bool bz[N]; using namespace std; struct node { int f[N][N]; friend node operator *(node a,node b) { node c; fo(i,1,n) { fo(j,1,n) { c.f[i][j]=-INF; fo(k,1,n) { int v=a.f[i][k]+b.f[k][j]; if(v>c.f[i][j]) c.f[i][j]=v; } } } return c; } }a[16],d,d1; bool pd(int lq) { if(lq==-1) { fo(i,1,n) if(d1.f[i][i]>0) return 1; return 0; } else { fo(i,1,n) if(a[lq].f[i][i]>0) return 1; return 0; } } int main() { cin>>n>>m; fo(i,1,n) { fo(j,1,n) { a[0].f[i][j]=-INF; } a[0].f[i][i]=0; } fo(i,1,m) { int x,y,p1,p2; scanf("%d%d%d%d",&x,&y,&p1,&p2); a[0].f[x][y]=p2-p1; } int k=0; d1=a[k]; while(!pd(k)) { a[k+1]=a[k]*a[k]; k++; } int k1=k-1,v=1<<(k-1); d1=d=a[k1]; while(!pd(-1)) { if(k1>1) k1--; d1=d*a[k1]; while(k1>0&&pd(-1)) k1--,d1=d*a[k1]; v+=(1<<k1); d=d1; } printf("%d",v); int ans=0; fo(i,1,n) ans=max(ans,d.f[i][i]); printf(" %d\n",ans); }