美食家

題目大意

給你一個有向圖，邊權(quán)為經(jīng)過所需時間
每個點有一個點權(quán)，有些點還有有特殊的點權(quán)
當(dāng)你到達(dá)一個點后，可以獲得該點的點權(quán)（重復(fù)經(jīng)過可以重復(fù)獲得，但不能停留），若在某個時間到某個點，則可獲得該特殊點權(quán)
現(xiàn)在問你從點1出發(fā)走，在時間T回到1得到的最大點權(quán)和是多少

輸入樣例#1

3 4 11 0 1 3 4 1 2 1 2 1 3 2 3 2 3 1 4

輸出樣例#1

13

輸入樣例#2

4 8 16 3 3 1 2 4 1 2 1 1 3 1 1 3 2 3 4 3 2 3 2 3 2 1 4 2 1 4 1 5 3 3 5 1 2 5 5 4 20

輸出樣例#2

39

樣例解釋#1

對于上圖，小 W 一種為期 11 天的可行旅游方案為 $1\to 2\to 1\to 2\to 3\to 1$

第 0 天，小 $W$ 從城市 1 開始旅行，獲得愉悅值 1 并向城市 2 出發(fā)。
第 1 天，小 $W$ 到達(dá)城市 2，獲得愉悅值 3 并向城市 1 出發(fā)。
第 4 天，小 $W$ 到達(dá)城市 1，獲得愉悅值 1 并向城市 2 出發(fā)。
第 5 天，小 $W$ 到達(dá)城市 2，獲得愉悅值 3 并向城市 3 出發(fā)。
第 7 天，小 $W$ 到達(dá)城市 3，獲得愉悅值 4 并向城市 1 出發(fā)。
第 11 天，小 $W$ 到達(dá)城市 1，獲得愉悅值 1 并結(jié)束旅行。
小 W 在該旅行中獲得的愉悅值之和為 13。

樣例解釋#2

最優(yōu)方案為 $1\to 3\to 4\to 2\to 3\to 4\to 1$

第 0 天，小 $W$ 從城市 1 開始旅行，獲得愉悅值 3 并沿道路 3 通行。
第 2 天，小 $W$ 到達(dá)城市 3，獲得愉悅值 2 并沿道路 4 通行。
第 5 天，小 $W$ 到達(dá)城市 4，由于美食節(jié)獲得愉悅值 20+4 并沿道路 7 通行。
第 6 天，小 $W$ 到達(dá)城市 2，獲得愉悅值 1 并沿道路 5 通行。
第 8 天，小 $W$ 到達(dá)城市 3，獲得愉悅值 2 并沿道路 4 通行。
第 11 天，小 $W$ 到達(dá)城市 4，獲得愉悅值 4 并沿道路 8 通行。
第 16 天，小 $W$ 到達(dá)城市 1，獲得愉悅值 3 并結(jié)束旅行。
小 W 獲得的愉悅值之和為 39。

數(shù)據(jù)范圍

$1\le n\le 50，n\le m\le 501，0\le k\le 200，1\le t_i\le T\le 10^9。$
$1\le w_i\le 5，1\le c_i\le 52501，1\le u_i,v_i,x_i\le n，1\le y_i\le 10^9$

解題思路

我們發(fā)現(xiàn)$w$很小,我們可以把一條邊分成若干長度為1的邊，這樣點最多只有250個
當(dāng)沒有特殊點權(quán)時
我們可以用鄰接矩陣跑矩陣乘法
時間$O((nw{)}^{3}logT)$
如果有特殊點權(quán)時直接暴力跑矩陣乘法那時間是$O((nw{)}^{3}klogT)$
會TLE
我們與處理出$f_i=A^{2^i}$
然后倍增求特殊點權(quán)到特殊點權(quán)之間的時間,然后加上相應(yīng)的權(quán)值
向量乘矩陣時間$O((nw{)}^2)$
總時間$O((nw{)}^{3}logT+(nw{)}^{2}klogT)$

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define p(x, y) ((x * 5) + (y)) using namespace std; ll n, m, t, k, x, y, z, w, nn, now, pw[35], a[260], b[260]; struct matrix {ll a[260][260]; }f[35]; struct node {ll t, v, s; }q[210]; bool cmp(node a, node b) {return a.t < b.t; } matrix jc(matrix &a) {matrix b;memset(b.a, 0xcf, sizeof(b.a));for (ll i = 0; i < nn; ++i)for (ll j = 0; j < nn; ++j)for (ll k = 0; k < nn; ++k)b.a[i][j] = max(b.a[i][j], a.a[i][k] + a.a[k][j]);//矩陣乘矩陣return b; } void js(matrix &b) {ll c[260];memcpy(c, a, sizeof(a));memset(a, 0xcf, sizeof(a));for (ll i = 0; i < nn; ++i)for (ll j = 0; j < nn; ++j)a[j] = max(a[j], c[i] + b.a[i][j]);//向量乘矩陣return; } void power(ll x) {for (ll i = 0; i <= w; ++i)if (x&pw[i]) js(f[i]);return; } int main() {scanf("%lld%lld%lld%lld", &n, &m, &t, &k);nn = n * 5;memset(f[0].a, 0xcf, sizeof(f[0].a));for (ll i = 0; i < n; ++i){scanf("%lld", &b[i]);for (ll j = 1; j < 5; ++j)f[0].a[p(i, j)][p(i, j - 1)] = 0;//拆分點}for (ll i = 1; i <= m; ++i){scanf("%lld%lld%lld", &x, &y, &z);x--;y--;f[0].a[p(x, 0)][p(y, z - 1)] = b[y];//連邊}pw[0] = 1;while(pw[w] * 2 <= t){w++;pw[w] = pw[w - 1] * 2;f[w] = jc(f[w - 1]);//計算f}for (ll i = 1; i <= k; ++i)scanf("%lld%lld%lld", &q[i].t, &q[i].v, &q[i].s), q[i].v--;sort(q + 1, q + 1 + k, cmp);q[++k] = (node){t, 0, 0};memset(a, 0xcf, sizeof(a));a[0] = b[0];for (ll i = 1; i <= k; ++i){power(q[i].t - now);//倍增a[p(q[i].v, 0)] += q[i].s;now = q[i].t;}if (a[0] < 0) printf("-1");else printf("%lld", a[0]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【矩阵乘法】【倍增】美食家（luogu 6772）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。