图论——分层图

Steadywelkin · 2021-03-11 14:39:37 · 个人记录

分层图

适用场景：

一些图论题，比如最短路、网络流等，题目对边的权值提供可选的操作，比如可以将一定数量的边权减半，在此基础上求解最优解。

算法思路：

根据是否进行题目提供的操作以及操作次数的不同，会产生非常多的情况，如果考虑何时使用操作，情况更是多。如果将在图上求解最短路看成是在二维平面上进行的，引入进行操作的次数 k 做为第三维，那么这个三维空间就理应可以包含所有的情况，便可以在这个三维空间上解决问题。

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

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

那么对于分层图的构建步骤可以描述为：

1、先将图复制成 k+1 份 (0-k)

2、对于图中的每一条边 (u,v) 从 u_i 到 v_(i+1) 建立与题目所给操作相对应的边 (i=0,1,…,k)

P3831 [SHOI2012]回家的路

以此题为例，我们可以将行和列分开来考虑，因为只有在中转车站会发生变化，所以我们只记录中转车站之间的花费：

• 同一行和同一列的花费
• 中转的花费（分层）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
typedef long long ll;

inline int read()
{
    int a=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())
        a=(a<<3)+(a<<1)+ch-'0';
    return a*f;
}

void write(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);
    putchar((x%10)^48);
}

inline void writen(int x)
{write(x);puts("");}

const int mod=1e9+7;
const int N=2e5+5;
const int INF=0x3f3f3f3f;

struct point{int x,y,id;}p[N<<2];
struct edge{int to,next,cost;}e[N<<2];
int head[N<<2],cnt,dis[N<<2];
int start,endk,n,m;
bool vis[N];

inline void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].cost=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline bool cmp1(const point& a,const point& b)
{
    if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}
inline bool cmp2(const point& a,const point& b)
{
    if(a.y==b.y) return a.x<b.x;
    else return a.y<b.y;
}

inline int Dij(void)
{
    memset(dis,INF,sizeof(dis));
    dis[start]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(-dis[m-1],start));
    while(!q.empty())
    {
        pair<int,int> u=q.top();q.pop();
        vis[u.second]=true;
        for(int i=head[u.second];i;i=e[i].next)
        {
            int v=e[i].to;
            if(vis[v])continue;
            if(dis[v]>dis[u.second]+e[i].cost)
            {
                dis[v]=dis[u.second]+e[i].cost;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
    return dis[endk];
}

signed main()
{
    n=read();m=read()+2;
    start=m-1,endk=m;
    for(int i=1;i<=m;i++)
    {
        p[i].x=read();
        p[i].y=read();
        p[i].id=i;
        if(i==start||i==endk)
        {
            add(i,i+m,0);
            add(i+m,i,0);
            continue;
        }
        add(i,i+m,1);
        add(i+m,i,1);
    }
    sort(p+1,p+m+1,cmp1);
    for(int i=1;i<m;i++)
    {
        if(p[i].x!=p[i+1].x)continue;
        add(p[i].id,p[i+1].id,(p[i+1].y-p[i].y)*2);
        add(p[i+1].id,p[i].id,(p[i+1].y-p[i].y)*2);
    }
    sort(p+1,p+m+1,cmp2);
    for(int i=1;i<m;i++)
    {
        if(p[i].y!=p[i+1].y)continue;
        add(p[i].id+m,p[i+1].id+m,(p[i+1].x-p[i].x)*2);
        add(p[i+1].id+m,p[i].id+m,(p[i+1].x-p[i].x)*2);
    }
    int ans=Dij();
    writen(ans==INF?-1:ans);
    return 0;
}