水资源监控能力建设 网站,巨量广告投放平台,企业级网站内容管理系统,wordpress 迅雷下载地址美食家
题目大意
给你一个有向图#xff0c;边权为经过所需时间 每个点有一个点权#xff0c;有些点还有有特殊的点权 当你到达一个点后#xff0c;可以获得该点的点权#xff08;重复经过可以重复获得#xff0c;但不能停留#xff09;#xff0c;若在某个时间到某个…美食家
题目大意
给你一个有向图边权为经过所需时间 每个点有一个点权有些点还有有特殊的点权 当你到达一个点后可以获得该点的点权重复经过可以重复获得但不能停留若在某个时间到某个点则可获得该特殊点权 现在问你从点1出发走在时间T回到1得到的最大点权和是多少
输入样例#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→2→1→2→3→11 \to 2 \to 1 \to 2 \to 3 \to 11→2→1→2→3→1
第 0 天小 WWW 从城市 1 开始旅行获得愉悦值 1 并向城市 2 出发。 第 1 天小 WWW 到达城市 2获得愉悦值 3 并向城市 1 出发。 第 4 天小 WWW 到达城市 1获得愉悦值 1 并向城市 2 出发。 第 5 天小 WWW 到达城市 2获得愉悦值 3 并向城市 3 出发。 第 7 天小 WWW 到达城市 3获得愉悦值 4 并向城市 1 出发。 第 11 天小 WWW 到达城市 1获得愉悦值 1 并结束旅行。 小 W 在该旅行中获得的愉悦值之和为 13。
样例解释#2
最优方案为 1→3→4→2→3→4→11 \to 3 \to 4 \to 2 \to 3 \to 4 \to 11→3→4→2→3→4→1
第 0 天小 WWW 从城市 1 开始旅行获得愉悦值 3 并沿道路 3 通行。 第 2 天小 WWW 到达城市 3获得愉悦值 2 并沿道路 4 通行。 第 5 天小 WWW 到达城市 4由于美食节获得愉悦值 204 并沿道路 7 通行。 第 6 天小 WWW 到达城市 2获得愉悦值 1 并沿道路 5 通行。 第 8 天小 WWW 到达城市 3获得愉悦值 2 并沿道路 4 通行。 第 11 天小 WWW 到达城市 4获得愉悦值 4 并沿道路 8 通行。 第 16 天小 WWW 到达城市 1获得愉悦值 3 并结束旅行。 小 W 获得的愉悦值之和为 39。
数据范围
1≤n≤50n≤m≤5010≤k≤2001≤ti≤T≤109。1 \leq n \leq 50n \leq m \leq 5010 \leq k \leq 2001 \leq t_i \leq T \leq 10^9 。1≤n≤50n≤m≤5010≤k≤2001≤ti≤T≤109。 1≤wi≤51≤ci≤525011≤ui,vi,xi≤n1≤yi≤1091 \leq w_i \leq 51 \leq c_i \leq 525011 \leq u_i, v_i, x_i \leq n1 \leq y_i \leq 10^91≤wi≤51≤ci≤525011≤ui,vi,xi≤n1≤yi≤109
解题思路
我们发现www很小,我们可以把一条边分成若干长度为1的边这样点最多只有250个 当没有特殊点权时 我们可以用邻接矩阵跑矩阵乘法 时间O((nw)3logT)O((nw)^3 logT)O((nw)3logT) 如果有特殊点权时直接暴力跑矩阵乘法那时间是O((nw)3klogT)O((nw)^3 k\ logT)O((nw)3k logT) 会TLE 我们与处理出fiA2if_iA^{2^i}fiA2i 然后倍增求特殊点权到特殊点权之间的时间,然后加上相应的权值 向量乘矩阵时间O((nw)2)O((nw)^2)O((nw)2) 总时间O((nw)3logT(nw)2klogT)O((nw)^3\ logT\ \ (nw)^2k\ logT)O((nw)3 logT (nw)2k logT)
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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 (xpw[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;
}
