文章目錄

• • • 題目解答
    • 題目鏈接

題目解答

來源：acwing

分析：
題目給定n個(gè)點(diǎn)和m條邊，要求最多選擇n條邊，使得1到n連通，然后每段路同時(shí)開工，求最小工時(shí)。換句話說，求的是連通路上最大邊權(quán)最小。

這題可以用二分來做。為什么呢？

假設(shè)最大邊權(quán)在數(shù)軸上的A點(diǎn)（邊長為a）能夠解決該題，那么換句話說，就是連通路徑上，所有邊長都是小于等于a。

作為題目，1到n點(diǎn)不會(huì)只有最佳的路徑連通，還會(huì)有其他路徑連通，只不過邊權(quán)會(huì)大一點(diǎn)。也就是說，對(duì)于數(shù)軸上A點(diǎn)右邊（長度都大于a），也是可以使得1到n連通的。而A點(diǎn)左邊的點(diǎn)是不能使之連通的（否則的話，最優(yōu)解就不是邊長a啦）。

所以，滿足這個(gè)性質(zhì)（某個(gè)點(diǎn)的一邊滿足條件，而另一邊不滿足條件）的題目，可以用二分查找來枚舉最優(yōu)邊權(quán)mid。

也就是說，對(duì)于枚舉的邊權(quán)mid，我們只走邊權(quán)小于等于mid 的邊，看是否1到n連通,并且走過的邊數(shù)小于等于n。如果連通，說明枚舉的mid大了，讓r = mid；否則說明枚舉的最優(yōu)邊權(quán)小了，應(yīng)該讓l = mid +1;

換個(gè)角度，構(gòu)造兩張圖，一張是原圖，另一張是邊權(quán)為1的圖，這樣在遍歷原圖的邊權(quán)小于mid時(shí)，說明這條路可以走，即在第二張圖中可以選擇這條路，我們?cè)诘诙垐D中求最短距離！這樣做有什么好處呢？在第二張圖中所有的邊權(quán)都是1，然后bfs求最短路即可，只要到n號(hào)點(diǎn)的最短路小于等于n（在原圖中的含義是走過了小于等于n條邊），這就說明該mid是滿足條件（連通，并且所選的邊權(quán)都小于等于mid）的，可以讓r= mid，遍歷更小的mid，從而不斷向最優(yōu)解靠近，求出最優(yōu)解。

ac代碼

#include<bits/stdc++.h> using namespace std;const int N = 100010, M = 400010;int n, m; int h[N], e[M],w[M], ne[M], idx; int dist[N]; int q[N]; void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } // 求1號(hào)點(diǎn)到n號(hào)點(diǎn)的最短路：邊權(quán)為1 // 返回值為最短路，含義是：從1號(hào)點(diǎn)到n號(hào)點(diǎn)使用的邊權(quán)小于等于mid 的條數(shù) //如果 返回值 == 6，說明從1號(hào)點(diǎn)到n號(hào)點(diǎn)，使用邊權(quán)小于等于mid的邊的條數(shù)為6條 int bfs(int mid){memset(dist, 0x3f, sizeof dist);dist[1] = 0;int hh = 0, tt = 0;q[0] = 1;while( hh <= tt){int t = q[hh ++];for(int i = h[t]; ~i; i = ne[i]){if(w[i] > mid) continue;int j = e[i];if(dist[j] > dist[t] + 1){dist[j] = dist[t] + 1;q[++tt] = j;}}}return dist[n]; }int main(){cin >> n >> m;memset(h, -1, sizeof h);while(m --){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}// 二分，枚舉合適的最優(yōu)邊權(quán)int l = 0, r = 1e6;while(l < r){int mid = l + r >> 1;if(bfs(mid) <= n) r = mid;else l = mid + 1;}//輸出二分出來的分界點(diǎn)，二分退出時(shí)l == rcout << r << endl; }

題目鏈接

https://www.acwing.com/problem/content/description/3248/

總結(jié)

以上是生活随笔為你收集整理的CSP认证201703-4地铁修建[C++题解]：连通路径上的最大边权最小、bfs求边权为1的最短路、二分查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。