2023年7月30日发(作者：)

分层图例题+模板分层图本质是在遍历图的过程中，有k条特殊边（包括但不限于，权重为0、逆向、权重减半等）。这时，我们只需建⽴k层图，每层图均与原图相同，每层图之间连接特殊边（权值为0的边、权值减半的边等）。模板⼀题意：有k不超过k条免费的边，求最⼩花费。算法：分层图+地杰斯特拉注意：每层图的终点均需要连接⼀条免费边，避免k值⼤于路径。#include #define pii pairusing namespace std;const int N = 1000000 + 10, M = 10000000 + 10;int e[M], ne[M], h[N], w[M], idx;bool st[N];int dis[N];int n, p, k;int start, ed;void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;}void dij() { memset(dis, 0x3f, sizeof dis); dis[start] = 0; priority_queue, greater> pq; ({0, start}); while (()) { auto t = (); (); int ver = , d = ; if (st[ver]) continue; st[ver] = true; // cout< dis[ver] + w[i]) { dis[j] = dis[ver] + w[i]; ({dis[j], j}); // cout<> n >> p >> k; cin >> start >> ed; memset(h, -1, sizeof h); for (int i = 1; i <= p; i++) { int a, b, l; cin >> a >> b >> l; add(a, b, l), add(b, a, l); for (int j = 1; j <= k; j++) { add(a + (j - 1) * n, b + j * n, 0), add(b + (j - 1) * n, a + j * n, 0); //上层到下层的双向边 add(a + j * n, b + j * n, l), add(b + j * n, a + j * n, l); //下层的双向边 } } for (int i = 1; i <= k; i++) { add((i-1) * n+ed, (i) * n +ed, 0); } dij(); cout << dis[k*n + ed] << endl; return 0;}其他例题：P4822、P2939、P3199模板⼆题意：从A点买⼊、B点卖出的最⼤收益题解：每层各节点之间的边权为0，表⽰连通性。1层与2层之间边权为价格的相反数，表⽰买⼊、2层与3层之间边权为价值，表⽰买⼊。使⽤SPFA计算从1号点到n号点的边权最⼤值。#include#define pii pairusing namespace std;const int N=100000*3+10, M=100000*2*10;int h[N],e[M],ne[M],w[M],idx;int dis[N];bool st[N];int n,m;void add(int a,int b,int c=0){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}void spfa(){ memset(dis,-0x3f,sizeof dis); queueq; (1); st[1]=true; dis[1]=0; while(()){ int t=(); (); st[t]=false; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(dis[j]>n>>m; memset(h,-1,sizeof h); for(int i=1;i<=n;i++){ int c; cin>>c; add(i,i+n,-c), add(i+n,i+2*n,c); } for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; if(z==1){ add(x,y), add(x+n,y+n), add(x+2*n,y+2*n); } else{ add(x,y), add(x+n,y+n), add(x+2*n,y+2*n); add(y,x), add(y+n,x+n), add(y+2*n,x+2*n); } } spfa(); cout<