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

简谈分层图

分层图是一个处理对边存在额外操作的较好的处理方式。
这里引入一道例题,在正常的最短路中,你可以挑选k条路不需要花费时间,那么最小总花费是多少
存在一种 d p dp dp的处理方式, d p [ i ] [ j ] dp[i][j] dp[i][j]表示到第i个节点用了j次免费, d p [ n ] [ 0 k ] dp[n][0~k] dp[n][0 k]即为答案。
那么怎么去转移呢, d p [ v ] [ j ] = m i n ( d p [ u ] [ j − 1 ] , d p [ u ] [ j ] + u − > v ) dp[v][j]=min(dp[u][j-1],dp[u][j]+u->v) dp[v][j]=min(dp[u][j1],dp[u][j]+u>v)
我们可以把其转换成k+1个图,分别代表用了几次免费机会的图,并且免费是不断用的次数增加的,也就是说 i i i个图和第 j j j个图有单向边相连,边权为0,代表用了一次免费机会
如何去添加这些边呢,就是将 i − > j i->j i>j在每张图都加上,同时 i − > j + n i->j+n i>j+n也加上(同样在每张图)。
这里我用 ( ( k − 1 ) n + 1 − > k n ) ((k-1)n+1 -> kn) ((k1)n+1>kn)表示第 k k k层的节点。
简要模板如下:

int n,m,k;
const int maxn = 10000000;
const int maxm = 20000000;
struct Edge{int from,to;ll dist;Edge(){}Edge(int _from,int _to,ll _dist):from(_from),to(_to),dist(_dist){}
};
Edge ed[maxm];int he[maxn],ne[maxm],etop=1;
void insert(int u,int v,ll w){ed[etop]=Edge(u,v,w);ne[etop]=he[u];he[u]=etop++;}void add_edge(int u,int v,ll w){for(int i=u,j=v;i<=u+k*n;i+=n,j+=n)insert(i,j,w);for(int i=u,j=v+n;j<=v+k*n;i+=n,j+=n)insert(i,j,0);
}ll d[maxn];
bool vis[maxn];
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
void dijkstra(int s){memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));d[s]=0;q.push(make_pair(0, s));while(!q.empty()){int now = q.top().second;q.pop();if(!vis[now]){vis[now] = true;for(int i = he[now]; i; i = ne[i]){Edge& e = ed[i];if(d[e.to] > d[now] + e.dist){d[e.to] = d[now] + e.dist;q.push(make_pair(d[e.to], e.to));}}}}
}

代码很简单,就是加上了边,所以分层图只是一种思想,没必要死记硬背。
但是这样的代码会 m l e mle mle,主要在于大量使用了一些不必要的点和边。
其实每次我们只需要对相邻层进行转移即可,其他都可以映射到初始图进行。
d [ i ] [ p ] d[i][p] d[i][p]表示到第 i i i个点,使用了 p p p次免费机会。
每次松弛的时候,对同一层松弛,同时判断是否还有免费机会,如果有,对下一层也松弛。

int n,m,k;
const int maxn = 100000;
const int maxm = 400010;
struct Edge{int from,to;ll dist;Edge(){}Edge(int _from,int _to,ll _dist):from(_from),to(_to),dist(_dist){}
};
Edge ed[maxm];int he[maxn],ne[maxm],etop=1;
void insert(int u,int v,ll w){ed[etop]=Edge(u,v,w);ne[etop]=he[u];he[u]=etop++;}ll d[maxn][30];
bool vis[maxn][30];
struct node{int to,level;ll cost;friend bool operator < (node a,node b){return a.cost>b.cost;}
};
priority_queue<node>q;void dijkstra(int s){memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));d[s][0]=0;q.push(node{s,0,0});while(!q.empty()){int now = q.top().to,p=q.top().level;        //cout<<d[now][p]<<" "<<q.size()<<endl;q.pop();if(!vis[now][p]){vis[now][p] = true;for(int i = he[now]; i; i = ne[i]){Edge& e = ed[i];if(!vis[e.to][p]&&d[e.to][p]>d[now][p]+e.dist){d[e.to][p]=d[now][p]+e.dist;q.push(node{e.to,p,d[e.to][p]});}if(p<k&&!vis[e.to][p+1]&&d[e.to][p+1]>d[now][p]){d[e.to][p+1]=d[now][p];q.push(node{e.to,p+1,d[e.to][p+1]});}}}}
}

http://www.taodudu.cc/news/show-6309757.html

相关文章:

  • 数据流图-2(分层数据流图)
  • 流程图分级、分类、分层
  • 什么是分层架构
  • 链路聚合的原理以及配置
  • 链路聚合—3种模式
  • 链路聚合及配置
  • 交换机之间的链路聚合
  • 链路聚合与链路捆绑
  • 链路聚合和LACP
  • 链路聚合(二层链路聚合划分)
  • 链路聚合—3种模式 详细
  • 【技术分享】链路聚合
  • 链路聚合详解
  • 链路聚合的作用与实例
  • 链路聚合原理及配置过程
  • 链路聚合(eth-trunk)
  • 链路聚合的定义、链路聚合的概念和基本术语、链路聚合的特点
  • 基于vue编写的2048小游戏
  • 用Qt开发小游戏《愤怒的小鸟》
  • [效率提升]webstorm配置Prettier:代码自动格式,格式化时清除空行,修改使用代码模板
  • WebStorm+Vue-cli 配置alias 点击跳转无效问题
  • JavaScript葵花宝典(基础)
  • js Console 对象 - Kaiqisan
  • JS_01_变量_数据类型
  • vanilla_使用Vanilla JavaScript构建Cookie库
  • 笔记 - JavaScript - 超哥视频
  • JS知识点总结(全)
  • Vue.js + Vuex + TypeScript 实战项目开发与项目优化
  • node.js 从基础到操作数据库
  • vscode css智能补全_在 Webstorm 伤透我的心后,我决定尝试 VS Code