当前位置: 首页 > news >正文

网站默认图福州网站seo优化公司

网站默认图,福州网站seo优化公司,绵阳集团网站建设,做网站公司流程美食家 题目大意 给你一个有向图#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}fi​A2i 然后倍增求特殊点权到特殊点权之间的时间,然后加上相应的权值 向量乘矩阵时间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; }
http://wiki.neutronadmin.com/news/20002/

相关文章:

  • net网站建设教程建设房地产公司网站的费用
  • 杭州网站站长统计代码
  • 27岁了想学网站建设做网站一般工资如何
  • 郑州公司网站开发怎么修改wordpress目录名字
  • 中咨城建设计南京网站外贸页面网站制作
  • 网站应用程序池布朗新风 中企动力提供网站建设
  • 设计素材网站模板如果在wordpress
  • 网站开发 q3687474wordpress设置联系表格
  • 安陆市城乡建设局网站谷歌网站提交
  • 为什么建设银行网站怎么制作公众号长图
  • 常州网站建设推广去哪里找做网站
  • 叠石桥网站建设宁波网站建设信息推荐
  • dw做的网站怎样做成手机版的win8风格企业网站
  • 美食论坛网站模板智能家居网站开发
  • 各大网站黑白文章 百度网站创建及发展历史
  • 网站群 米拓wordpress文章发布审核
  • 网站的权限管理怎么做商城网站都有什么功能
  • 手机app界面设计软件怎样优化网络速度
  • 网站建设方向课程怎么做好网站
  • 海北营销网站建设公司成都软件开发网站建设
  • 网站建设与栏目设置成都高端网页设计公司
  • 网站建设项目网络图佛山 做网站
  • 仿商城版淘宝客网站源码公司管理系统名称大全
  • 简约个人网站建立网站的英文
  • 网站特效 站长oa系统多少钱一套
  • 建设银行校园招聘网站wordpress中文维护插件
  • 龙岩做网站的公司重庆旅游
  • 马鞍山北京网站建设怎么查看自己的网站是否被百度收录
  • 网站下载免费新版群晖 wordpress 怎么映射到外网
  • 可信赖的邵阳网站建设wordpress 数据库解析