Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

分层图

算法

发布于：Apr 30, 2022

更新于：Aug 13, 2024

次浏览

前言

前几天考试了发现这个东西完全不会欸……学了又忘真是讨厌至极 QAQ 所以又在网上找着看了看写一篇博客备忘。

学习笔记真的很有用！

分层图

这个很容易理解，来源就是在一些最短路的问题上题目又加了比如说主角可以用传送宝石进行折跃之类的问题（针对），即可以选择k条边把这些边的边权变为零。

怎么样解决呢？可以在原图的基础上多复制k个相同的图，并用k条边把图之间的边用0边权边相连。就是：

于是就有人说了，复制一个图不是需要很多的空间吗，直接爆掉了怎么办(╯‵□′)╯︵┻━┻

（是的有这种可能所以图k不能太大）

其实因为都是复制的好像不需要很多空间，因为图基本上都是一样的。所以只需要用二维数组 dis 记录就行了~（所以可以理解为把二维的图变成了三维，然后有 \(k\) 个 \(0\) 边权的虫洞可以折跃（雾））

只需要走一次就行。这里我用 dijkstrua~

例题

题目我是从这里搬的。代码是我的。但是我没有数据所以有可能是错的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<utility>
#include<functional>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e4,maxm=5e4,maxk=10,INF=~0U>>1;
int n,m,k,start,end;
struct edge{
    int to,next,dis;
}e[4*maxm*(maxk+1)+maxk+1];
int ecnt,head[maxn*(maxk+1)+1];
void addedge(int from,int to,int dis)
{      //这种赋值写法必须加强制类型转换，c11可以不用
    e[++ecnt]=(edge){to,head[from],dis};head[from]=ecnt;
}

void read(int &x)
{
    bool flag = false;
    char c;
    do c=getchar();while(c!='-' and (c < '0' || c > '9'));
    if(c=='-')flag=true;
    else x+=c-'0';
    c=getchar();
    while(c>='0' and c<='9')x*=10,x+=c-'0',c=getchar();
}

inline void readin()
{
    read(n);read(m);read(k);read(start);read(end);
    for(int i=1;i<=m;i++)
    {
        int a,b,w;
        read(a);read(b);read(w);
        //重点来了，开始建边权为零的边 
        for(int j=0;j<=k;j++)
        {
            addedge(a+n*j,b+n*j,w);addedge(b+n*j,a+n*j,w);
            //这两行是建图并复制图，共建造k+1个图 
            if(j!=k)//小心别建到虚无中去~ 
            {
                addedge(a+n*j,b+n*(j+1),0);addedge(b+n*j,a+n*(j+1),0);
                //这两行是在图之间建边权为0的边 
            }
        }
    }
}
//分层图的核心已经完成，下面是开心的dijkstrua时间 
int dis[maxn*(maxk+1)];
bool vis[maxn*(maxk+1)];
typedef pair<int,int> pairr;
void dijskra()
{
    priority_queue <pairr,vector<pairr >,greater<pairr > > q;
    q.push(make_pair(0,start));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[start]=0;
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=head[u];i;i=e[i].next)
            {
                int to=e[i].to;
                if(dis[u]+e[i].dis<dis[to])
                {
                    dis[to]=dis[u]+e[i].dis;
                    q.push(make_pair(dis[to],to));
                }
            }
        }
    }
}
int main()
{
    readin();
    dijskra();
    cout<<dis[end];
    return 0;
}

P4568 [JLOI2011]飞行路线

如果掌握了方法的话这个题和上一道基本上是一模一样的，只需要把板子粘下来就行了。不过我们可以从上一道题发现建的边数太多了啊喂……所以我们这次用一下前面提到的二元数组记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cstdio>
#include<utility>
#include<functional>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e4,maxm=5e4,maxk=10,INF=~0U>>1;
int n,m,k,start,end;
struct edge{
    int to,next,dis;
}e[4*maxm*(maxk+1)+maxk+1];
int ecnt,head[maxn*(maxk+1)+1];
void addedge(int from,int to,int dis)
{
    e[++ecnt]=(edge){to,head[from],dis};head[from]=ecnt;
}

void read(int &x)
{
    bool flag = false;
    char c;
    do c=getchar();while(c!='-' and (c < '0' || c > '9'));
    if(c=='-')flag=true;
    else x=c-'0';
    c=getchar();
    while(c>='0' and c<='9')x*=10,x+=c-'0',c=getchar();
}
int  read2()
{
    int x;
    char c=getchar();
    while(c<'0' or c>'9')c=getchar();
    x=c-'0';c=getchar();
    while(c>='0' and c<='9')
    x*=10,x+=c-'0',c=getchar();
    return x;
}

void readin()
{
//    read(n);read(m);read(k);read(start);read(end);
    n=read2(),m=read2(),k=read2(),start=read2(),end=read2();
    for(int i=0;i<m;i++)
    {
        int a,b,w;
//        read(a);read(b);read(w);
        a=read2(),b=read2(),w=read2();
        //重点来了，开始建边权为零的边
        for(int j=0;j<=k;j++)
        {
            addedge(a+n*j,b+n*j,w);addedge(b+n*j,a+n*j,w);
            //这两行是建图并复制图，共建造k+1个图 
            if(j!=k)//小心别建到虚无中去~ 
            {
                addedge(a+n*j,b+n*(j+1),0);addedge(b+n*j,a+n*(j+1),0);
                //这两行是在图之间建边权为0的边 
            }
        }
    }
}
//分层图的核心已经完成，下面是开心的dijskrua时间 
int dis[maxn*(maxk+1)];
bool vis[maxn*(maxk+1)];
typedef pair<int,int> pairr;
void dijkstra()
{
    priority_queue <pairr,vector<pairr >,greater<pairr > > q;
    q.push(make_pair(0,start));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[start]=0;
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=head[u];i;i=e[i].next)
            {
                int to=e[i].to;
                if(dis[u]+e[i].dis<dis[to])
                {
                    dis[to]=dis[u]+e[i].dis;
                    q.push(make_pair(dis[to],to));
                }
            }
        }
    }
}
int main()
{
    readin();
    dijkstra();
    for(int i=1;i<=k;++i)
    {
        addedge(end+(i-1)*n,end+i*n,0);
    }
    cout<<dis[end+k*n];
    return 0;
}

飞行路线1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<utility>
 4 #include<queue>
 5 #include<functional>
 6 #include<vector>
 7 #include<algorithm>
 8 #include<cstring>
 9 using namespace std;
10 const int maxn=1e4,maxm=5*1e4,maxk=10;
11 typedef pair<int,int> pairr;
12 struct edge{
13     int to,nxt,dis;
14 }e[maxm*4];
15 int n,m,k,start,end,d[maxn][maxk+1];
16 bool vis[maxn][maxk+1];
17 inline int read()
18 {
19     int x=0;char c=getchar();
20     while(!isdigit(c))c=getchar();
21     while(isdigit(c))x=x*10+c-'0',c=getchar();
22     return x;
23 }
24 int ecnt,head[maxn];
25 inline void addedge(int from,int to,int dis)
26 {
27     e[++ecnt]=(edge){to,head[from],dis},head[from]=ecnt;
28 }
29 
30 void input()
31 {
32     n=read(),m=read(),k=read(),start=read(),end=read();
33     for(int i=0;i<m;i++)
34     {
35         int from=read(),to=read(),dis=read();
36         addedge(from,to ,dis);addedge(to,from,dis);
37     }
38 }
39 
40 void dijkstra()
41 {
42     priority_queue <pairr,vector<pairr>,greater<pairr > > q;
43     memset(d,0x3f3f3f3f,sizeof(d));
44     d[start][0]=0;
45     q.push(make_pair(0,start));
46     while(!q.empty())
47     {
48         int v=q.top().second;q.pop();
49         int kk=v/n;                        //kk标记当前已用的k次数 
50         v%=n;                            //v变为图中点的位置 
51         for(register int i=head[v];i;i=e[i].nxt)
52         {
53             int u=e[i].to,w=e[i].dis;
54             if(d[v][kk]+w<d[u][kk]) 
55             {
56                 d[u][kk]=d[v][kk]+e[i].dis;
57                 q.push(make_pair(d[u][kk],u+(kk)*n));
58             }
59             if(kk==k)continue;//用完了就算了QAQ 
60             if(d[u][kk+1]>d[v][kk])//可以用而且不穿越解非最优就传送 
61             {
62                 d[u][kk+1]=d[v][kk];
63                 q.push(make_pair(d[u][kk+1],u+(kk+1)*n));//这里编号乘一下以记录层数（因为没有结构体就酱紫了） 
64             }
65         }
66     }
67 }
68 int main()
69 {
70     input();
71     dijkstra();
72 //    cout<<d[end][k];//输出全部用过达到的距离 
73 //这个输出被最后一组数据hack了，好像是不用用完k个的。所以我们找个min
74     int ans=0x3f3f3f3f; 
75     for(int i=0;i<=k;i++)ans=min(ans,d[end][i]);
76     printf("%d\n",ans);
77     return 0;
78 }

笔者用的是pair记录，好像用结构体能更清楚一些并记录层数，其实没什么区别的。大家随意（干杯）

更新于：Aug 13, 2024

博客园

OI

图论

给小狼留言