problem

有一個n個點m條邊的連通無向圖（無重邊、無自環），點的編號為1~n。每條邊都有一個正的邊權，并且每條邊邊權互不相同（即數據保證該圖的最小生成樹唯一）。
如果只是求最小生成樹，那么Ohyee覺得太簡單了，于是他決定考考你。
對于每條邊(u,v)都進行詢問：
——如果該邊在最小生成樹上，那么輸出“Ohyee”；
——如果該邊不在最小生成樹上，那么輸出最小生成樹上u,v兩點路徑中邊權的最小值。

Input

第一行輸入兩個整數n,m(2<=n<=100000,n-1<=m<=200000)
接下來m行，每行輸入三個整數u,v,w。u,v表示該邊連接點的編號，w是邊權。
(1<=w<=1000000000)

Output

輸出一共m行，按照輸入的邊的順序回答每條邊的詢問。

Input

4 4
1 2 2
2 3 5
3 4 7
4 1 3

Output

Ohyee
Ohyee
2
Ohyee

Limitation

1s 256MB

Hint

原圖最小生成樹中的邊是(1,2,2) (2,3,5) (4,1,3)
對于輸入的第三條邊(3,4,7)，樹上3->4的路徑是3->2->1->4，邊權分別是5,2,3，最小值是2。

思路

最小生成樹和樹上路徑信息維護的結合，兩個模板套在一起即可

代碼示例

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+50; const int maxm=2e5+50; const int inf=0x3fffffff;int n,m;//n為點數 m為邊數struct eee{//解決lcaint from,to,dist;eee(int u,int v,int w):from(u),to(v),dist(w){} };vector<eee> edges;//邊的具體信息 vector<int> GG[maxn];//邊的編號void addEdge(int u,int v,int w){//vector鄰接表edges.push_back(eee(u,v,w));edges.push_back(eee(v,u,w));int size=edges.size();GG[u].push_back(size-2);GG[v].push_back(size-1); }const int maxlog=30; int grand[maxn][maxlog]; int gmax[maxn][maxlog]; int depth[maxn]; int s;//倍增最大步數 int root;//根節點void dfs(int x)//預處理 {for(int i=1;i<=s;++i){grand[x][i]=grand[grand[x][i-1]][i-1];gmax[x][i]=max(gmax[x][i-1],gmax[grand[x][i-1]][i-1]);if(!grand[x][i]) break;}for(int i=0;i<GG[x].size();i++){eee & e=edges[GG[x][i]];if(e.to!=grand[x][0]){depth[e.to]=depth[x]+1;grand[e.to][0]=x;gmax[e.to][0]=e.dist;dfs(e.to);}} }void init() {s=floor(log(n+0.0)/log(2.0));depth[0]=-1;//memset(depth,0,sizeof(depth));memset(grand,0,sizeof(grand));memset(gmax,0,sizeof(gmax));root=1;dfs(root);//以1為根結點建樹 }int lca(int a,int b,int &maxx)//最大值 {if(depth[a]>depth[b]) swap(a,b);maxx=gmax[b][0];//之前的bug,應該放更深的bint dre=depth[b]-depth[a];for(int i=s;i>=0;--i){if(dre&(1<<i)) maxx=max(maxx,gmax[b][i]),b=grand[b][i];}if(a==b) return a;for(int i=s;i>=0;i--)if(grand[a][i]!=grand[b][i]){maxx=max(maxx,gmax[a][i]),maxx=max(maxx,gmax[b][i]);a=grand[a][i],b=grand[b][i];}maxx=max(maxx,gmax[a][0]);maxx=max(maxx,gmax[b][0]);return grand[a][0]; }typedef struct{//邊集數組int beg;int endd;int weight;int flag;//1表示在 0表示不在int order;//進來時的順序 }Edge;bool cmp(Edge a,Edge b)//邊集數組排序 {return a.weight<b.weight; }bool cmp1(Edge a,Edge b)//原位置排序 {return a.order<b.order; }typedef struct{Edge xiang[maxm];//邊的信息int numVertexes,numEdges;//頂點數和邊數 }MGraph;MGraph G;void CreateMGraph() {for(int i=0;i<m;++i){cin>>G.xiang[i].beg>>G.xiang[i].endd>>G.xiang[i].weight;G.xiang[i].order=i;}G.numEdges=m;G.numVertexes=n;sort(G.xiang,G.xiang+m,cmp); }int parent[maxm];//輔助并查集int Find(int f)//查找連線頂點的尾部下標 {return parent[f]!=f?parent[f]=Find(parent[f]):f; }void MiniSpanTree_Kruskal() {int nn,mm;//int parent[maxm];//定義一數組用來判斷邊與邊是否形成環路for(int i=0;i<G.numVertexes;++i)parent[i]=i;//初始化數組值為ifor(int i=0;i<G.numEdges;++i){//循環每一條邊nn=Find(G.xiang[i].beg);mm=Find(G.xiang[i].endd);if(nn!=mm){//假如n與m不等，說明此邊沒有與現有生成樹形成環路parent[nn]=mm;//將此邊的結尾頂點放入下標為起點的parent中//表示此頂點已經在生成樹集合中//printf("在：(%d,%d) %d\n",G.xiang[i].beg,G.xiang[i].endd,G.xiang[i].weight);//sum+=G.xiang[i].weight;G.xiang[i].flag=1;addEdge(G.xiang[i].beg,G.xiang[i].endd,1000000001-G.xiang[i].weight);//進入lca，注意求最小值，所以拿大值減后求最大值//cout<<G.xiang[i].beg<<' '<<G.xiang[i].endd<<' '<<1000000001-G.xiang[i].weight<<endl;}else{G.xiang[i].flag=0;//不在}//else printf("不在：(%d,%d) %d\n",G.xiang[i].beg,G.xiang[i].endd,G.xiang[i].weight);}//cout<<sum<<endl;//路徑和 }int main() {ios::sync_with_stdio(false);cin>>n>>m;CreateMGraph();//for(int i=0;i<G.numEdges;++i) cout<<G.xiang[i].beg<<" "<<G.xiang[i].endd<<" "<<G.xiang[i].weight<<endl;//cout<<G.numEdges<<G.numVertexes<<endl;MiniSpanTree_Kruskal();//for(int i=0;i<G.numVertexes;++i)//cout<<parent[i]<<' ';sort(G.xiang,G.xiang+m,cmp1);init();int maxx;//生成樹上兩點間最短邊權for(int i=0;i<m;++i){if(G.xiang[i].flag==1){cout<<"Ohyee"<<endl;}else{lca(G.xiang[i].beg,G.xiang[i].endd,maxx);//cout<<lca(u,v,maxx,sum)<<endl;cout<<1000000001-maxx<<endl;//再減去即為最小值}}return 0; }

總結

以上是生活随笔為你收集整理的17AHU排位赛2 A题（最小生成树、LCA维护树上路径）的全部內容，希望文章能夠幫你解決所遇到的問題。

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