洛谷 P6772 - [NOI2020]美食家（广义矩阵快速幂）

题面传送门

题意：

有一张 \(n\) 个点 \(m\) 条边的有向图，第 \(0\) 天的时候你在 \(1\) 号城市，第 \(T\) 天的时候你要回到 \(1\) 号城市。

每条边上的边权表示从城市 \(u_i\) 到达 \(v_i\) 需要的天数。

你每次到达城市 \(i\) 就会获得 \(c_i\) 的愉悦值

另外有 \(k\) 个三元组 \((t_i,x_i,y_i)\) 表示如果你第 \(t_i\) 天到达城市 \(x_i\) 就可以额外获得 \(y_i\) 的愉悦值

求最大愉悦值。

\(n \leq 50\)，\(T \leq 10^9\)，\(k \leq 200\)，\(w_i \leq 5\)

大家好，这就是那个考场上想到广义矩阵快速幂却没写的人。

感觉这题就是 P6190+CF576D+P3715

当时三题一题都没做过，现在三题都做过了回来看这题就很简单了。

朴素 \(dp\) 特别容易，\(dp_{i,j}\) 表示经过 \(i\) 天到达 \(j\) 号城市获得的最大愉悦值。

考虑优化，先假设 \(k=0\)，所有 \(w_i\) 都等于 \(1\)。

那么就有 \(dp_{t,v_i}=\max\{dp_{t-1,u_i}+c_{v_i}\}\)

用广义矩阵乘法 \(c_{i,j}=\max\{a_{i,k}+b_{k,j}\}\) 的方式转移即可。

再考虑 \(w_i\neq 1\) 的情况。我们可以将转移矩阵扩充到 \((5n)\times(5n)\)，用一个 \(1\times 5n\) 的矩阵记录 \(dp_{i},dp_{i-1},dp_{i-2},dp_{i-3},dp_{i-4}\) 的值进行转移。

最后考虑 \(k\neq 0\)，把所有美食节按 \(t_i\) 从小到大排序，然后分段转移。

这样是 \(k(5n)^3\log T\) 的，显然不行。

不过一个 \(n\times m\) 的矩阵与 \(m\times k\) 的矩阵相乘，所谓的 \(n^3\)，实际上是 \(nmk\)，也就是说，我们可以预处理出转移矩阵的 \(2^k\) 的幂，然后每次转移的时候用那个 \(1\times (5n)\) 的矩阵与其做一遍矩阵乘法，这样复杂度就降到了 \((5n)^2k\log T\)。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fz(i,a,b) for(int i=a;i<=b;i++)

#define fd(i,a,b) for(int i=a;i>=b;i--)

#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

template<typename T> void read(T &x){

	char c=getchar();T neg=1;

	while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	x*=neg;

}

const int MAXN=50;

const int MAXK=200;

const int LOG_T=30;

int n,m,T,k,c[MAXN+5];

struct mat{

	int N,M;ll a[MAXN*5+5][MAXN*5+5];

	mat(){for(int i=1;i<=MAXN*5;i++) for(int j=1;j<=MAXN*5;j++) a[i][j]=-1e18;}

	friend mat operator *(mat x,mat y){

		mat ret;ret.N=x.N;ret.M=y.M;

		for(int i=1;i<=x.N;i++) for(int j=1;j<=x.M;j++)

			for(int k=1;k<=y.M;k++) chkmax(ret.a[i][j],x.a[i][k]+y.a[k][j]);

		return ret;

	}

} tr[LOG_T+2],cur;

struct event{

	int t,x,y;

	friend bool operator <(event a,event b){

		return a.t<b.t;

	}

} a[MAXK+5];

int main(){

//	freopen("deligacy.in","r",stdin);freopen("deligacy.out","w",stdout);

	scanf("%d%d%d%d",&n,&m,&T,&k);

	for(int i=1;i<=n;i++) scanf("%d",&c[i]);

	for(int i=1;i<=n;i++) for(int j=0;j<4;j++) tr[0].a[j*n+n+i][j*n+i]=0;

	tr[0].N=tr[0].M=5*n;

	for(int i=1;i<=m;i++){

		int u,v,w;scanf("%d%d%d",&u,&v,&w);

		chkmax(tr[0].a[(5-w)*n+u][4*n+v],c[v]);

	}

	cur.N=1;cur.M=5*n;cur.a[1][4*n+1]=c[1];

	for(int i=1;i<=LOG_T;i++) tr[i]=tr[i-1]*tr[i-1];

	int pre=0;

	for(int i=1;i<=k;i++) scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);

	sort(a+1,a+k+1);

	for(int i=1;i<=k;i++){

		int dis=a[i].t-pre;pre=a[i].t;

		for(int j=0;j<=LOG_T;j++) if(dis>>j&1) cur=cur*tr[j];

		cur.a[1][n*4+a[i].x]+=a[i].y;

	}

	int dis=T-pre;

	for(int j=0;j<=LOG_T;j++) if(dis>>j&1) cur=cur*tr[j];

	if(cur.a[1][4*n+1]<0) puts("-1");

	else printf("%lld\n",cur.a[1][4*n+1]);

	return 0;

}

巴特西

洛谷 P6772 - [NOI2020]美食家（广义矩阵快速幂）

最新文章

热门文章