【图论】【分层图】分层图总结
Singercoder
·
2020-02-16 01:03:23
·
个人记录
算法介绍
算法简介：分层图最短路，指对于一张含有多重状态的图，我们可以建出等同于状态数数目的图，然后根据题意找到不同状态的两张图之间的关系，直接最短路解决。
使用范围：含有多种状态的同一张图。
实现细节：如果不建多张图，我们可能想到在原图上根据状态进行修改（枚举），但这样难以做到两张相邻状态图之间的联系。故有：
建立原图。
建立其他状态下的同一张图。
根据两个状态相关图之间的关系，连接该两张图之间的边。
例题分析（p4568)
题意：对于一张有n个点（0~n-1）和m条无向边（u,v,w)(w>=0)的图，可以将其中k条边权降为0，求出s到t的最短路。(k<=20)
分析：
最简单的思路就是在原图上修改（枚举），然后分别最短路。然而如上文所述，这样不能有效利用两种相邻状态图之间的联系。（NP算法)
运用分层图优化，分别建出同样的原图和k张状态图，其中的k张状态图分别代表使用1次降权机会之后的状态。考虑第i和第i+1张图之间的关系，可知在第i张图中每有1条边u->v，就需要建一条边u（第i张图中的）->v（第i+1张图中的），权值为0。即可以将该边权降至0并沿该边方向移动。（注意k次降权不一定全部使用，所以每一层的t都可能为最优解）
#include
#include
#include
#include
#include
#define inf 0x3fffffff
using namespace std;
const int MAXN=10010;
const int MAXM=50010;
const int MAXK=20;
int n,m,k,s,t;
int en=-1,pre[MAXN*MAXK];
struct edge
{
int u,v,w,next;
};edge e[MAXM*MAXK<<2];
inline void insert(int u,int v,int w)
{
e[++en].next=pre[u];
pre[u]=en;
e[en].u=u;
e[en].v=v;
e[en].w=w;
}
inline void input()
{
memset(pre,-1,sizeof(pre));
scanf("%d %d %d %d %d",&n,&m,&k,&s,&t);
int u,v,w;
for(int i=1;i<=m;++i)
{
scanf("%d %d %d",&u,&v,&w);
for(int j=0;j<=k;++j)
{
insert(j*n+u,j*n+v,w);
insert(j*n+v,j*n+u,w);
if(j!=k)
{
insert(j*n+u,(j+1)*n+v,0);
insert(j*n+v,(j+1)*n+u,0);
}
}
}
}
int dis[MAXN*MAXK];
struct cmp
{
bool operator ()(const pair
{
return a.first>b.first;
}
};
inline void solve()
{
for(int i=0;i<=k*n+n-1;++i)dis[i]=inf;
priority_queue
dis[s]=0;q.push(make_pair(dis[s],s));
pair
int u,v;
while(!q.empty())
{
p=q.top();q.pop();
if(p.first!=dis[p.second])continue;
u=p.second;
for(int i=pre[u];i!=-1;i=e[i].next)
{
v=e[i].v;
if(dis[u]+e[i].w { dis[v]=dis[u]+e[i].w; q.push(make_pair(dis[v],v)); } } } } inline void output() { int ans=inf; for(int i=0;i<=k;++i)ans=min(ans,dis[i*n+t]); printf("%d\n",ans); } int main() { // freopen("in.txt","r",stdin); input(); solve(); output(); return 0; }