旅游网站 分析,高级网站设计,沈阳百度网站的优点,网站空间与域名的关系前置知识 简单的图论知识 简单的#xff44;#xff50;知识 使用标志 你机智的发现了这是一道图论题,并且出现了类似于N次免费/花费变化的字样,大部分就是分层图最短路了. 它不是不是很难#xff0c;就是那种#xff0c;那种看起来很凶神恶煞的#xff0c;你知道么#… 前置知识 简单的图论知识 简单的知识 使用标志 你机智的发现了这是一道图论题,并且出现了类似于N次免费/花费变化的字样,大部分就是分层图最短路了. 它不是不是很难就是那种那种看起来很凶神恶煞的你知道么好的我不是专业的但其实挺人畜无害的flag也用可能是我做题少 为什么这么做 DP类思路解释 当你发现传统图论求最短路的方法无法维护有K个变化的时候你就要想办法通过一些方法使你的算法可以去多维护一个数据此时很顺利利用DP处理后效性的方法之一加一维来解决这个方法把原数组的vis[i]变为vis[i][j]表示你在经过i个点时你用了j次免死金牌的这种状态你是否曾经有过dis[i]变为dis[i][j]表示你在经过i个点时你用了j次免死金牌时你所走出的路是怎样的这时你再在迪杰斯特拉求解或SPFA求解时把使用多少次免死金牌这种次数记录在堆或队列中即可 我只写过两次SPFA所以我就不把SPFA的代码贴上去了怕出锅 1 struct ziji{int dis,where,cnt;};2 3 bool operator (const ziji a,const ziji b){return a.disb.dis;}4 5 priority_queuezijiq;6 //迪杰斯特拉核心7 dis[1][0]0;q.push((ziji){0,1,0});8 //此处不要加vis[1][0]1,会WA9 while(!q.empty()){
10
11 int whichq.top().where,numq.top().cnt;q.pop();
12
13 if(vis[which][num]) continue;vis[which][num]1;
14
15 for(int ihead[which];i;inxt[i]){
16 int yver[i];
17
18 if(numkdis[y][num1]dis[which][num]val[i]/2)
19
20 dis[y][num1]dis[which][num]val[i]/2,
21
22 q.push((ziji){dis[y][num1],y,num1});
23
24 if(dis[y][num]dis[which][num]val[i])
25
26 dis[y][num]dis[which][num]val[i],
27
28 q.push((ziji){dis[y][num],y,num});
29 }
30 }
31 } 构造分层图的思想 每一次你对路径的处理就相当于改变的图的部分此时你要尽量维护图不变所以可以利用主席树不同版本构造的思路来想就相当于每一次改变路径就来一次次元飞行每一个次元的图都是相对完整的每一次你都站在一个世界线收束的拐角点去择优选择你要到哪一个次元里去提前构造出每一个次元,再跑一遍最短路(没写过QAQ但在网上找到了一份比较靠谱的代码我加了点注释贴了上来 1 for(int i 1; i m; i )2 {//以bzoj2662冻结为例3 int aa,bb,cc;4 scanf(%d%d%d,aa,bb,cc);5 for(int j 0; j k; j )//依据题意建K层6 {//每一层的建图操作7 build(j*naa,j*nbb,cc);8 build(j*nbb,j*naa,cc);9 if(j k)
10 {//如果可以用减速卡的话
11 build(j*naa ,(j1)*nbb,cc/2);
12 build(j*nbb ,(j1)*naa,cc/2);
13 }
14 }
15 }//剩下的dijkstra正常跑最短路就好
16 dijkstra(1);
17 int ans 214748364;
18 for(int i 0; i k; i )
19 ans min(ans,dis[i*nn]);
20 //因为有多层所以要在多层里求最小值 NOTICE 后者对空间要求略大于前者,而前者对时间要求略大于后者,请OIERS依题使用 最后,国际惯例,谢谢大家,有问题欢迎之处一起讨论 转载于:https://www.cnblogs.com/fallen-down/p/11210966.html
