分层图

齐天の小猴 · 2018-10-26 16:53:01 · 个人记录

分层图一般用于作图论题

第一次认识分层图：P1073 最优贸易

解析：更详细 --> 题解

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define N 100010
#define M 500010
using namespace std;
struct Edge
{
    int node,len;
};
int n,m,pri[N],x,y,z;
int head[M],cnt,dis[M];
vector<Edge> g[M];
queue<int> q;
bool vis[M];
void add(int u,int v)
{
    g[u].push_back((Edge){v,0});//第一图层 从1到n 
    g[u+n].push_back((Edge){v+n,0});//第二图层 从n+1到2*n 
    g[u+2*n].push_back((Edge){v+2*n,0});//第三图层 从2*n+1到3*n 
    g[u].push_back((Edge){v+n,-pri[u]});//赋值 
    g[u+n].push_back((Edge){v+2*n,pri[u]});
    return;
}
template<typename int_t>
void readx(int_t& x)
{
    x=0; int_t k=1; char ch=0;
    while(ch<'0'||ch>'9') {ch=getchar();if(ch=='-') k=-1;}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=k;
}
void spfa()
{
    for(int i=1;i<=n;i++) dis[i]=-0x3f3f3f3f;
    q.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        vis[k]=0;
        int l=g[k].size();
        for(int i=0;i<l;i++)
        {
            Edge x=g[k][i];
            if(dis[x.node]<dis[k]+x.len)
            {
                dis[x.node]=dis[k]+x.len;
                if(!vis[x.node])
                {
                    vis[x.node]=1;
                    q.push(x.node);
                }
            }
        }
    }
}
int main()
{
    readx(n);readx(m);
    for(int i=1;i<=n;i++) readx(pri[i]);
    for(int i=1;i<=m;i++)
    {
        readx(x);readx(y);readx(z);
        if(z==1) add(x,y);
        if(z==2) {add(x,y); add(y,x);}
    }
    g[n].push_back((Edge){3*n+1,0});
    g[n*3].push_back((Edge){3*n+1,0});
    n=3*n+1;
    spfa();
    printf("%d",dis[n]);
    return 0;
}

分层图最短路：在分层图上解决最短路问题摘自 --> 分层最短路

第一种思想：dp（动态规划）

一般模型：

在一张图上，有k次机会可以通过一条边而不需要计算权值，求从起点到终点的最短路。

思想：

将一个点拆分为k+1个点，分别表示到这个点时，免费次数消耗了0次、1次...k次

这样就可以把这k个点想象成对应dp的不同状态

dis[i][j]表示到第i个点时，消耗了j次免费机会多的最短路

to 要到达的点； f 父亲节点

dis[to][j]=min(dis[x][j]+val(x,to),dis[x][j-1])

因为我们跑最短路时是从前向后跑，也就是当前状态推出后继状态，所以实际上我们可以推出两个可能状态

如果我们消耗了免费机会

dis[to][j] = min{dis[x][j - 1]}

如果我们没消耗免费过路权

dis[to][j] = min{dis[x][j] + val(x, to)}

这就提醒我们，我们的队列在加入到达某个点的同时，要分别记录到达这个点时的两种不同的状态，以免造成情况遗漏

也就是q[i][j]表示到第i个点时，第i个点在j的情况下我们消耗了几次免费过路权，j为0或是1,0表示没有消耗免费过路权，1表示消耗了免费过路权

到这里我们就能与上面的拆点联系上了，我们想，到了终点时，可能有：用了0次免费过路权，用了1次免费过路权，用了2次，用了3次....用了k次

也就是k+1种可能状态，此时我们把这k+1种状态，每种状态都想象成原本的这个点拆分出来的一个点，也就相当于这个点拆分出了k+1个点，就和上面接上了

然后我们合理外推，对于每一个点都可能出现这样的情况，也就相当于每一个点都拆分成了k+1个点，这n*(k+1)个点之间彼此连接，跑最短路

第二种思想：分层图

例题（对我来说真的是超难啊）

P2939 改造路

P4011 孤岛营救

分层图