【洛谷P1967】 貨車運輸

重做NOIP提高組ing...

+傳送門-洛谷P1967+

---

?

◇ 題目(copy from 洛谷)

題目描述

A國有n座城市，編號從1到n，城市之間有m條雙向道路。每一條道路對車輛都有重量限制，簡稱限重?，F(xiàn)在有q輛貨車在運輸貨物，司機們想知道每輛車在不超過車輛限重的情況下，最多能運多重的貨物。

輸入輸出格式

輸入格式：

第一行有兩個用一個空格隔開的整數(shù)n,m，表示A國有n座城市和m條道路。

接下來 mm行每行3個整數(shù)x, y, z，每兩個整數(shù)之間用一個空格隔開，表示從x號城市到y(tǒng)號城市有一條限重為z的道路。注意：x不等于y，兩座城市之間可能有多條道路 。

接下來一行有一個整數(shù)q，表示有q輛貨車需要運貨。

接下來 q 行，每行兩個整數(shù) x、y，之間用一個空格隔開，表示一輛貨車需要從 x 城市運輸貨物到 y 城市，注意： x 不等于 y 。

輸出格式：

共有q行，每行一個整數(shù)，表示對于每一輛貨車，它的最大載重是多少。如果貨車不能到達目的地，輸出?1。

輸入輸出樣例

輸入樣例#1：?

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

輸出樣例#1：

3
-1
3

---

?

◇ 解析

算是一道比較經(jīng)典的題目了吧……NOIP還是有很多好題的

根據(jù)題目我們可以知道我們的目的是找一條從x到y(tǒng)的路徑，使得路徑上的最小值最大。找路徑……樹剖，Dijkstra，SPFA，LCA（搜索就別想了），然后我們發(fā)現(xiàn)LCA是里面最好寫的?（看起來樹剖也可以，但是并不想寫線段樹，調(diào)試很麻煩）。

很容易想到盡量走大的邊。根據(jù)這個思路，我們可以通過貪心進一步得出重邊（注意題目有重邊）時，取較大的一條。由于這是一個有多個連通塊的圖，我們單獨考慮一個連通塊：

現(xiàn)在我們相當(dāng)于要選擇該連通塊的一些邊，使得連通塊內(nèi)的點能夠互相到達，且選擇的邊的最小值盡量大——就是一個最大生成樹！

為什么是一棵樹呢？——因為樹的每一個節(jié)點都互相連通，并不破壞原來連通塊的結(jié)構(gòu)，且每個節(jié)點都只會選擇以它為端點的一條邊（多次經(jīng)過同一個點沒有意義），就相當(dāng)于每個節(jié)點有唯一父親（根節(jié)點除外），這樣也就形成了樹的結(jié)構(gòu)。

為什么生成最大？——最大生成樹的選擇方案一定是所有選擇方案（合法的）中盡可能大的一個，即其他方案的最小邊必然小于等于最大生成樹的最小邊，根據(jù)貪心的思路判定最大生成樹更優(yōu)。

那么現(xiàn)在就非常明顯了，可以用Kruskal算法來做，對于每個連通塊都建立一棵最大生成樹。聽起來很麻煩？其實操作的時候并不需要考慮每個連通塊，直接像生成一個連通圖的最大生成樹這樣對于題目所給的圖生成樹就可以了——因為不同的連通塊所屬的并查集也不一樣，不會互相影響。只是說現(xiàn)在不一定要選擇(n-1)條邊了，可能要少一些。如果直接這樣想的話我們會生成一個無根樹，這樣不能用LCA，于是就把樹中編號最小節(jié)點作為根節(jié)點。

接下來就是處理出 LCA 所需要的 fa[u][k]:節(jié)點u的第 2^k 輩祖先（空為0）和 dep[u]:節(jié)點u的深度，當(dāng)然對于這道題，我們還需要再加上一個數(shù)組 MinEdg[u][k]:從u到u的第 2^k 輩祖先的路徑上的最小邊。先用一個DFS可以處理出 fa[i][0],dep[i]以及MinEdg[i][0]，即父親、深度以及從父親到兒子的邊權(quán)。再對于每個節(jié)點處理出 fa,MinEdg ，fa的處理就不講了（LCA基礎(chǔ)，可以先學(xué)一學(xué)再看），MinEdg的處理類似與fa—— u->fa[u][k] 分成 u->fa[u][k-1] 和 fa[u][k-1]->fa[u][k]，則 MinEdg[u][k]=min(MinEdg[u][k-1],MinEdg[fa[u][k-1]][k-1])。（啊哈？?）?

然后就是LCA的操作了，這里重點講MinEdg怎么轉(zhuǎn)換到答案Min。（默認(rèn)u比v深）在把u移動到v的同一層時，更新 Min=min(Min,MinEdg[u][i])，這樣就把u移動到與v同層的路徑的最小值統(tǒng)計出來了。接下來u,v一起移動，則 Min 同時要根據(jù) u 和 v 的移動更新——Min=min( Min,min(MinEdg[u][i],MinEdg[v][i]) )。最后非常重要的一點?，我們只會把u,v移動到它們的LCA的下面一層，u->v的路徑實際上還有 u->LCA 和 LCA->v ，即 MinEdg[u][0] 和 MinEdg[v][0] ，所以最后 Min=min(Min,min(MinEdg[u][0],MinEdg[v][0]))。

結(jié)束了？別忘了判斷一下u和v是否在同一個連通塊里，可以用并查集，但是作者用的是找LCA，如果LCA為0，則u,v不連通。

---

?

◇ 源代碼

/*Lucky_Glass*/ #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std;const int M=50000,N=10000;struct ROAD { //存儲原圖上的邊 int u,v,wgt; //兩個端點u,v和權(quán)值wgt bool operator <(const ROAD ano)const {return wgt>ano.wgt; //按邊權(quán)從大到小排序 } } way[M+5]; int n,m,q,INF; int pre[N+5],dep[N+5],fa[N+5][25],MinEdg[N+5][25]; vector< pair<int,int> > lnk[N+5]; //生成樹后的連通關(guān)系（鄰接表） int FindPre(int u) { //并查集 if(pre[u]==u) return u;return pre[u]=FindPre(pre[u]); }void DFS(int u,int _fa,int _dep) {fa[u][0]=_fa;dep[u]=_dep; //直接計算fa,dep for(int i=0; i<lnk[u].size(); i++) {int v=lnk[u][i].first,wgt=lnk[u][i].second;if(v==_fa) continue;MinEdg[v][0]=wgt; //MinEdg[v][0] 就是從u->v的邊 DFS(v,u,_dep+1);} }void Prepare() {memset(MinEdg,0x3f,sizeof MinEdg); //賦極大值 INF=MinEdg[0][0];for(int i=1; i<=n; i++)if(!dep[i]) //即沒有訪問過，是一個新的連通塊 DFS(i,0,1),MinEdg[i][0]=INF; //樹的根沒有向上的邊，賦值INF for(int j=1; j<=20; j++)for(int i=1; i<=n; i++)fa[i][j]=fa[fa[i][j-1]][j-1],MinEdg[i][j]=min(MinEdg[fa[i][j-1]][j-1],MinEdg[i][j-1]);//把2^k分成兩段2^(k-1)計算 }pair<int,int> LCA(int u,int v) { //第一個返回值為LCA的編號，第二個返回值是路徑的最小邊 if(dep[u]<dep[v]) swap(u,v);int Min=INF;for(int i=20; i>=0; i--) //之前寫反了，一直過不了自己出的數(shù)據(jù)……if(dep[fa[u][i]]>=dep[v])Min=min(Min,MinEdg[u][i]),u=fa[u][i];if(u==v)return make_pair(u,Min);for(int i=20; i>=0; i--)if(fa[u][i]!=fa[v][i])Min=min(Min,min(MinEdg[u][i],MinEdg[v][i])),u=fa[u][i],v=fa[v][i];Min=min(Min,min(MinEdg[u][0],MinEdg[v][0])); //★important return make_pair(fa[u][0],Min); }int main() {freopen("truck.in","r",stdin);freopen("truck.out","w",stdout);scanf("%d%d",&n,&m);for(int i=0; i<m; i++)scanf("%d%d%d",&way[i].u,&way[i].v,&way[i].wgt);sort(way,way+m);for(int i=1; i<=n; i++) pre[i]=i;for(int cnt=1,i=0; cnt<n && i<m; i++) { //Kruskal，不一定要有n-1條邊，如果邊枚舉完就退出 int A=FindPre(way[i].u),B=FindPre(way[i].v);if(A!=B)pre[A]=B,lnk[way[i].u].push_back(make_pair(way[i].v,way[i].wgt)),lnk[way[i].v].push_back(make_pair(way[i].u,way[i].wgt)); //建立新圖 }Prepare();scanf("%d",&q);while(q--) {int u,v;scanf("%d%d",&u,&v);pair<int,int> res=LCA(u,v);if(res.first) printf("%d\n",res.second); //判斷連通 else printf("-1\n");}return 0; }

　　

---

?

The End

Thanks for reading!

- Lucky_Glass

（Tab：如果我有沒講清楚的地方可以直接在郵箱lucky_glass@foxmail.com email我，在周末我會盡量解答并完善博客~?）

轉(zhuǎn)載于:https://www.cnblogs.com/LuckyGlass-blog/p/9591652.html

總結(jié)

以上是生活随笔為你收集整理的【杂题总汇】NOIP2013(洛谷P1967) 货车运输的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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