前言

我考場（線上賽）切NOI的題了！

---

正題

題目鏈接:https://www.luogu.com.cn/problem/P6772

---

題目大意

$n$個點$m$條邊，每個城市有不同的愉悅值，從$1$出發，要求經過$T$的時間后回到點$1$(不能原地停留。

特別的是有$k$個美食節，在第$t_i$個時刻如果在第$x_i$個城市就可以額外獲得$y_i$的愉悅值，求路徑上最大愉悅值

---

解題思路

首先矩陣乘法變形后是可以求最長路的

之后之前有一道題目$[POI2015]WYC$【矩陣乘法,倍增】和這題很像，因為邊權最大只有5，所以可以將每個點分成$5$個點就可以跑矩陣乘法了。這樣有$250$個點，跑一次矩陣乘法是$O(250^3\log T)$，不考慮美食節的情況下可以過，但是如果有美食節時間復雜度就接近$O(k?250^3\log T)$顯然不可過。

然后之前有一道$NOIOnline$的題目$NOIOnline\#3$提高組魔法值正解是先預處理出$logT$個矩陣然后再用向量乘矩陣

我們就得出了解法，我們先預處理使得$F_i=A^{2^i}$，然后這樣我們用向量乘矩陣就是$O(n^2)$的，之后每次做矩陣到每一個美食節，然后對于在那一天的情況加上一個愉悅值即可，可以通過本題。

時間復雜度$:O((nw{)}^3\log T+(nw{)}^{2}k\log T)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define p(x,y) ((x)*5+(y)) #define ll long long using namespace std; const ll N=51; struct matrix{ll a[N*5][N*5]; }f[32]; struct node{ll t,x,y; }h[210]; ll n,m,T,k,tot,Size,a[N*5],p2[32],c[N*5]; matrix operator*(const matrix &a,const matrix &b){matrix c;memset(c.a,0xcf,sizeof(c.a));for(ll i=0;i<Size;i++)for(ll j=0;j<Size;j++)for(ll k=0;k<Size;k++)c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);return c; } void mul(matrix &b){memcpy(c,a,sizeof(c));memset(a,0xcf,sizeof(a));for(ll i=0;i<Size;i++)for(ll j=0;j<Size;j++)a[j]=max(a[j],b.a[i][j]+c[i]);return; } void power(ll b){for(ll i=0;i<=tot;i++)if(b&p2[i])mul(f[i]);return; } bool cmp(node x,node y) {return x.t<y.t;} int main() { // freopen("delicacy.in","r",stdin); // freopen("delicacy.out","w",stdout);scanf("%lld%lld%lld%lld",&n,&m,&T,&k);Size=n*5;memset(f[0].a,0xcf,sizeof(f[0].a));for(ll i=0;i<n;i++){scanf("%lld",&c[i]);for(ll j=0;j<4;j++)f[0].a[p(i,j+1)][p(i,j)]=0;}for(ll i=1;i<=m;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);x--;y--;f[0].a[p(x,0)][p(y,w-1)]=c[y];}p2[0]=1;while(p2[tot]*2<=T){tot++;p2[tot]=p2[tot-1]*2;f[tot]=f[tot-1]*f[tot-1];}for(ll i=1;i<=k;i++)scanf("%lld%lld%lld",&h[i].t,&h[i].x,&h[i].y),h[i].x--;sort(h+1,h+1+k,cmp);ll now=0;h[++k]=(node){T,0,0};memset(a,0xcf,sizeof(a));a[0]=c[0];for(ll i=1;i<=k;i++){power(h[i].t-now);a[p(h[i].x,0)]+=h[i].y;now=h[i].t;}if(a[0]<0)printf("-1");else printf("%lld",a[0]); }

總結

以上是生活随笔為你收集整理的P6772-[NOI2020]美食家【矩阵乘法,倍增】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。