前置知识

简单的图论知识

简单的ｄｐ知识

使用标志

你机智的发现了这是一道图论题,并且出现了类似于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.dis>b.dis;} 4  5 priority_queue
     
      q; 6 //迪杰斯特拉核心 7         dis[1][0]=0;q.push((ziji){
   0,1,0}); 8 　　　　　//此处不要加vis[1][0]=1,会WA 9         while(!q.empty()){10 11             int which=q.top().where,num=q.top().cnt;q.pop();12 13             if(vis[which][num]) continue;vis[which][num]=1;14 15             for(int i=head[which];i;i=nxt[i]){16                 int y=ver[i];17 18                 if(num
      
       dis[which][num]+val[i]/2)19 20                     dis[y][num+1]=dis[which][num]+val[i]/2,21 22                     q.push((ziji){dis[y][num+1],y,num+1});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*n+aa,j*n+bb,cc); 8             build(j*n+bb,j*n+aa,cc); 9             if(j < k)10             {
   //如果可以用减速卡的话11                 build(j*n+aa ,(j+1)*n+bb,cc/2);12                 build(j*n+bb ,(j+1)*n+aa,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*n+n]);20     //因为有多层，所以要在多层里求最小值

 

NOTICE  后者对空间要求略大于前者,而前者对时间要求略大于后者,请OIERS依题使用

最后,国际惯例,谢谢大家,有问题欢迎之处一起讨论