分層圖最短路
分層圖
分層圖確實(shí)是個(gè)不難的東西我也確實(shí)是一個(gè)菜雞...
簡(jiǎn)要介紹
分層圖常在圖論問(wèn)題中出現(xiàn)可任選K條邊更改邊權(quán)（變?yōu)?或是原來(lái)一半等）時(shí)應(yīng)用。
分層圖，就是在應(yīng)對(duì)這種問(wèn)題時(shí)，把原圖復(fù)制K層（總共K+1層）
每相鄰層之間用更改邊權(quán)后的邊連接對(duì)應(yīng)的點(diǎn)（代表進(jìn)行一次操作）
然后就可以在這個(gè)新圖中處理，得到問(wèn)題的最優(yōu)解
圖例如下
因?yàn)檫B接兩層的邊代表的是進(jìn)行了一次不可逆的邊權(quán)操作，所以都是有向邊
每層圖內(nèi)部的邊就是和原圖一樣了
簡(jiǎn)單說(shuō)明
可能有人會(huì)有疑問(wèn)，把圖復(fù)制K層后，空間和時(shí)間不會(huì)爆炸嘛？
雖然分層圖總共有K+1層圖
但因?yàn)槊繉佣贾皇菃渭兊膹?fù)制原圖
所以內(nèi)容都是一樣的，一般沒(méi)有必要新建圖
我們只需要用一個(gè)二維數(shù)組表示點(diǎn)編號(hào)及其所在層數(shù)
例如在求最短路時(shí)，用 dis[x][k] 表示分層圖中在k層的x點(diǎn)的最短距離
即原圖中進(jìn)行了k次邊權(quán)操作的 x 點(diǎn)最短距離
這樣就不需要新建圖了
（如果最后還是炸了，說(shuō)明正解大概不是分層圖）
例題
題目描述
Your are given an undirect connected graph.Every edge has a cost to pass.You should choose a path from S to T and you need to pay for all the edges in your path. However, you can choose at most k edges in the graph and change their costs to zero in the beginning. Please answer the minimal total cost you need to pay.
您將獲得一個(gè)無(wú)向連通圖。每條邊都有成本要通過(guò)。您應(yīng)該選擇一條從S到T的路徑，并且需要為路徑中的所有邊付費(fèi)。但是，您可以在圖中選擇最多k個(gè)邊，并在開(kāi)始時(shí)將其成本更改為零。請(qǐng)回答您需要支付的最低總費(fèi)用。（機(jī)翻）
輸入描述:
The first line contains five integers n,m,S,T,K.
For each of the following m lines, there are three integers a,b,l, meaning there is an edge that costs l between a and b.
n is the number of nodes and m is the number of edges.
第一行包含五個(gè)整數(shù)n，m，S，T，K。
對(duì)于以下m行中的每一行，有三個(gè)整數(shù)a，b，l，這意味著在a和b之間存在成本為l的邊。
n是節(jié)點(diǎn)數(shù)，m是邊數(shù)。
輸出描述:
An integer meaning the minimal total cost.
一個(gè)整數(shù)表示最小總成本。
示例1
輸入
3 2 1 3 1
1 2 1
2 3 2
輸出
1
備注:
1≤n,m≤1e3,1≤S,T,a,b≤n,0≤k≤m,1≤l≤1e6
Multiple edges and self loops are allowed.
來(lái)源：牛客網(wǎng)暑期多校第四場(chǎng)J題
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std; #define M 1000100 struct node { int to,next,w; }e[2*M]; typedef pair <int,int> p; priority_queue <p,vector<p>,greater<p> > q; int dis[1010][1010],head[M],s,t,n,m,k=0; int path[1010],cnt; bool vis[1010][1010]; void add(int u,int v,int w) { e[k].to=v; e[k].next=head[u]; e[k].w = w; head[u]=k++; } void dij() { for (int i=1;i<=n;i++) { for (int j=0;j<=k;j++) dis[i][j] = 0x7f7f7f7f; } memset(vis,0,sizeof vis); int now,son,x; dis[s][0] = 0; q.push(make_pair(0,s)); while ( q.size() ) { now = q.top().second; q.pop(); if ( now%n == 0 ) x = now/n-1,now=n; else x=now/n,now%=n; if ( vis[now][x] ) continue; vis[now][x] = 1; for (int i=head[now];~i;i=e[i].next) { son = e[i].to; if ( dis[now][x]+e[i].w<dis[son][x]) { dis[son][x] = dis[now][x]+e[i].w; q.push(make_pair(dis[son][x],son+n*x)); } if ( x != cnt ) { if ( dis[son][x+1] > dis[now][x]) { dis[son][x+1] = dis[now][x]; q.push(make_pair(dis[son][x+1],son+x*n+n)); } } } } } int main() { int a,b,c; memset(head,-1,sizeof head); scanf("%d%d%d%d%d",&n,&m,&s,&t,&cnt); for (int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } dij(); printf("%d\n",dis[t][cnt]); return 0; }
浙公網(wǎng)安備 33010602011771號(hào)