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

【图论基础】分层图

使用场景:经常在最短路,网络流等图论题中,通过一些规则可以修改边权而求得最优解。

理解:如果将在图上求解最短路看成是在二维平面上进行的,那么分层图的含义便是引入进行操作的次数 k 做为第三维,便可以在这个三维空间上解决问题。

每进行一次操作,除了操作的边,其他边没有任何变化,在 k=0,1,2,…,时图都是一样的,那么就将图复制成 k+1 份,第 i 层图代表进行了 i 次操作后的图。

每相邻两层图之间的联系,应该决定了一次操作是发生在哪条边上(何时进行操作)。根据操作的特点(对边权的修改)可以 i 层点到 i+1 层点的边来表示一次操作。

而这k次操作便是设立分层图的关键。

裸题

洛谷P4568

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#include <sstream>
#define LL long long
#define _for(i,j,k) for(int i=j;i<=k;i++)
#define for_(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int maxn = 1e4+5;
const int maxm = 1e5+5;
const int maxk = 10+1; 
const int inf = 1e9;
struct Edge{//edgeint v,d;bool operator<(const Edge& ort)const{return d>ort.d;}
};
int n,m,k,s,t;
Edge e[2*maxm*maxk];//graph
int head[maxn*maxk],net[2*maxm*maxk],cnt,dis[maxn*maxk];//邻接表
priority_queue<Edge> q;
void add_edge(int u,int v,int d){e[++cnt].v=v;e[cnt].d=d;net[cnt]=head[u];head[u]=cnt;
}
void dijkstral(int u){//dijkstral最短路模板_for(i,1,n*(k+1)) dis[i]=inf;dis[u]=0;q.push(Edge{u,0});Edge tm;while(!q.empty()){tm=q.top();q.pop();u=tm.v;if(dis[u]!=tm.d) continue;for(int i=head[u];i;i=net[i]){if(dis[e[i].v]>dis[u]+e[i].d){dis[e[i].v]=dis[u]+e[i].d;q.push(Edge{e[i].v,dis[e[i].v]});}}}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>k>>s>>t;s++;t++;int u,v,d;_for(i,1,m){//建分层图cin>>u>>v>>d;u++;v++;add_edge(u,v,d);add_edge(v,u,d);_for(j,1,k){add_edge(u+j*n,v+j*n,d);//每一层add_edge(v+j*n,u+j*n,d);add_edge(u+j*n-n,v+j*n,0);//层与层之间add_edge(v+j*n-n,u+j*n,0);}}dijkstral(s);int an=dis[t];_for(i,1,k){an=min(an,dis[t+i*n]);//k次操作内的最短路}cout<<an;return 0;
}


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

相关文章:

  • 数据分层(方法论)
  • 分层图[模板]
  • 食物链(分层图?)
  • 分层图总结(例题)
  • 拆点/分层图的使用
  • 分层架构简图
  • 数据分层简述
  • 简谈分层图
  • 数据流图-2(分层数据流图)
  • 流程图分级、分类、分层
  • 什么是分层架构
  • 链路聚合的原理以及配置
  • 链路聚合—3种模式
  • 链路聚合及配置
  • 交换机之间的链路聚合
  • 链路聚合与链路捆绑
  • 链路聚合和LACP
  • 链路聚合(二层链路聚合划分)
  • 链路聚合—3种模式 详细
  • 【技术分享】链路聚合
  • 链路聚合详解
  • 链路聚合的作用与实例
  • 链路聚合原理及配置过程
  • 链路聚合(eth-trunk)
  • 链路聚合的定义、链路聚合的概念和基本术语、链路聚合的特点
  • 基于vue编写的2048小游戏
  • 用Qt开发小游戏《愤怒的小鸟》
  • [效率提升]webstorm配置Prettier:代码自动格式,格式化时清除空行,修改使用代码模板
  • WebStorm+Vue-cli 配置alias 点击跳转无效问题
  • JavaScript葵花宝典(基础)