題意：

約翰一共有 N 個牧場.由 MM 條布滿塵埃的小徑連接。小徑可以雙向通行。每天早上約翰從牧場 1 出發到牧場 N 去給奶牛檢查身體。

通過每條小徑都需要消耗一定的時間。約翰打算升級其中 K 條小徑，使之成為高速公路。在高速公路上的通行幾乎是瞬間完成的，所以高速公路的通行時間為 0。

請幫助約翰決定對哪些小徑進行升級，使他每天從 1 號牧場到第 N 號牧場所花的時間最短。

題解：

參考題解“”
一直知道分層圖，但是沒用過，突然遇到一道分層圖的網絡流題目，發現自己忘了分層圖咋實現，趕緊拿來一道分層圖模板題做做
簡單說說什么是分層圖：
其實就是將一個平面的圖重新建圖，有好幾層
具體的說每層圖之間各自連邊與原圖一樣，但是相鄰的兩層圖之間根據原來的關系進行連邊
雖然是多層圖，但是用一維的關系就可以
比如：
當有3個點，3層圖時
1對應的就是 1+n 和 1+2 * n
2對應的就是 2+n 和 2+2 * n
…
當存在n個點，k層圖時，
1對應的就是1+n * 0, 1+ n* 1…1+n * (k-1)
而且每一層的圖都遵循只能從上面的圖到下一層圖，不能反過來
那建這么多層圖的目的是什么呢？
你可以理解成是一種嘗試，就比如本題，我們向下一層就代表改造一條道路
我們向下一層代表改造一條道路，我們不可能改造道路后再把它修回原來的樣子

我們要建多少層？
有k次機會，不難想出，我們要建k+1層

代碼：

#include<cstdio> #include<queue> #define read(x) scanf("%d",&x)//宏定義，個人習慣 #define INF 0x3f3f3f3f//偽極大值 using namespace std; typedef pair<int,int> pii;//個人習慣 struct Node {int head,dis; }node[210100];//數組大小注意 struct Edge {int to,len,next; }edge[4200100];//數組大小注意 int n,m,k,u,v,w,cnt,ans=INF<<1; void addEdge(int u,int v,int w) {edge[++cnt]={v,w,node[u].head};node[u].head=cnt; } //鏈式前向星存圖 void Dijkstra() {for(int i=1;i<=n*(k+1);i++){node[i].dis=INF;}//初始化時，要注意我們的點數已經不是n了，而是n*（k+1）node[1].dis=0;priority_queue<pii,vector<pii>,greater<pii> >q;//小根堆q.push({0,1});while(q.size()){pii tmp=q.top();q.pop();int d=tmp.first,u=tmp.second;if(d!=node[u].dis)continue;for(int e=node[u].head;e;e=edge[e].next){int v=edge[e].to;if(node[v].dis>edge[e].len+d){node[v].dis=edge[e].len+d;q.push({node[v].dis,v});}}} } //最短路板子不解釋 int main() {read(n),read(m),read(k);for(int i=1;i<=m;i++){read(u),read(v),read(w);for(int j=0;j<=k;j++){/*當j為0時，我們建立的是原圖的邊當j不為0時，我們建立的是分身的邊*/addEdge(u+j*n,v+j*n,w);addEdge(v+j*n,u+j*n,w);//上面兩行是每層圖之間，自身的點的連線，邊權不變if(j==k)break;/*為什么當j==k時，要退出循環呢？因為如果j==k時，還建下面的邊，那么就超出范圍了可以自行感性理解一下*/addEdge(u+j*n,v+(j+1)*n,0);addEdge(v+j*n,u+(j+1)*n,0);//這兩行建立的是層與層之間的邊，邊權為0}}Dijkstra();//跑最短路for(int i=0;i<=k;i++){ans=min(ans,node[n+i*n].dis);//統計每一層到n距離的最小值}printf("%d\n",ans);//輸出答案return 0; }

總結

以上是生活随笔為你收集整理的[USACO09FEB]Revamping Trails G的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。