\u4e00\u9053\u6700\u5927\u751f\u6210\u6811\u52a0LCA\u7684\u88f8\u9898\u3002
\n\u56e0\u4e3a\u662f\u6c42\u8def\u4e0a\u6743\u503c\u6700\u5c0f\u7684\u8fb9\u6743\u503c\u6700\u5927\uff0c\u6240\u4ee5\u53ef\u4ee5\u5728\u6700\u5927\u751f\u6210\u6811\u4e0a\u8dd1\u3002\u5f53\u7136\u4e8c\u5206\u7b54\u6848\u52a001BFS\u4e5f\u662f\u4e00\u79cd\u60f3\u6cd5\uff0c\u4e0d\u8fc7\u65f6\u95f4\u590d\u6742\u5ea6\u4e0d\u5bf9\u3002
\n\u90a3\u4e48\u5728\u6700\u5927\u751f\u6210\u6811\u4e0a\u5f88\u663e\u7136\u6700\u5927\u7684\u8def\u5f84\u4e0a\u8fb9\u6743\u503c\u6700\u5c0f\u3002
\n\u6240\u4ee5\u5728\u6700\u5927\u751f\u6210\u6811\u4e0a\u8dd1LCA\uff0c\u8bb0\u5f55\u6cbf\u9014\u8def\u5f84\u6700\u5927\u503c\u5373\u53ef\u3002
\n\u5f53\u7136\u8dd1\u6811\u5256\u4e5f\u662f\u53ef\u4ee5\u7684\uff0c\u4e0d\u8fc7\u5f88\u96be\u5199\u3002<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<algorithm>\r\n\r\nconst int INF = 0x3f3f3f3f;\r\n\r\nint n,m,q;\r\n\r\nint FA[10005];\r\ninline int fa( int X ){\r\n return X==FA[X]?X:(FA[X]=fa(FA[X]));\r\n}\r\ninline void mrg( int X, int Y ){\r\n X = fa( X ), Y = fa( Y );\r\n FA[X] = Y;\r\n}\r\n\r\nstruct ee0{\r\n int u;\r\n int v;\r\n int w;\r\n inline bool operator < (const ee0 &B)const{\r\n return w > B.w;\r\n }\r\n}e0[50005];\r\n\r\nstruct ee{\r\n int v;\r\n int w;\r\n int nxt;\r\n}e[20005];\r\nint h[10005],et=0;\r\ninline void Add(int U,int V,int W){\r\n e[++et] = (ee){V,W,h[U]};\r\n h[U] = et;\r\n}\r\n\r\nint fi[10005][20],fv[10005][20],dep[10005];\r\nbool vis[10005];\r\ninline void dfs(int X,int FTHR){\r\n for(int i=h[X];i;i=e[i].nxt){\r\n if(vis[e[i].v]){\r\n continue;\r\n }\r\n vis[e[i].v]=1;\r\n fi[e[i].v][0]=X;\r\n fv[e[i].v][0]=std::min(fv[e[i].v][0],e[i].w);\r\n dep[e[i].v]=dep[X]+1;\r\n dfs(e[i].v,X);\r\n }\r\n}\r\n\r\ninline int lca(int X,int Y){\r\n dep[X]<dep[Y]?(X^=Y^=X^=Y):0;\r\n int ans=INF,dlt;\r\n if(X==Y){\r\n return 0;\r\n }\r\n for(dlt=15;dlt>=0;--dlt){\r\n if(dep[X]-(1<<dlt)>=dep[Y]){\r\n ans=std::min(ans,fv[X][dlt]);\r\n X=fi[X][dlt];\r\n }\r\n } \r\n if(X==Y){\r\n return ans;\r\n }\r\n for(dlt=15;dlt>=0;--dlt){\r\n if(fi[X][dlt]!=fi[Y][dlt]){\r\n ans=std::min(ans,fv[X][dlt]);\r\n ans=std::min(ans,fv[Y][dlt]);\r\n X=fi[X][dlt],Y=fi[Y][dlt];\r\n }\r\n }\r\n ans=std::min(ans,fv[X][0]);\r\n ans=std::min(ans,fv[Y][0]);\r\n return ans;\r\n}\r\n\r\nvoid init(){\r\n scanf(\"%d%d\",&n,&m);\r\n for(int i=1;i<=m;++i){\r\n scanf(\"%d%d%d\",&e0[i].u,&e0[i].v,&e0[i].w);\r\n }\r\n for(int i=1;i<=n;++i){\r\n FA[i]=i;\r\n fv[i][0]=INF;\r\n }\r\n std::sort(e0+1,e0+1+m);\r\n for(int i=1;i<=m;++i){\r\n if(fa(e0[i].v)!=fa(e0[i].u)){\r\n Add(e0[i].u,e0[i].v,e0[i].w);\r\n Add(e0[i].v,e0[i].u,e0[i].w);\r\n mrg(e0[i].u,e0[i].v);\r\n }\r\n }\r\n for(int i=1;i<=n;++i){\r\n if(FA[i]==i){\r\n fi[i][0]=0;\r\n fv[i][0]=0;\r\n vis[i]=1;\r\n dfs(i,0);\r\n }\r\n }\r\n scanf(\"%d\",&q);\r\n for(int j=1;j<=15;++j){\r\n for(int i=1;i<=n;++i){\r\n fi[i][j]=fi[fi[i][j-1]][j-1];\r\n fv[i][j]=std::min(fv[i][j-1],fv[fi[i][j-1]][j-1]);\r\n }\r\n }\r\n int u,v;\r\n for(int i=1;i<=q;++i){\r\n scanf(\"%d%d\",&u,&v);\r\n if(fa(u)!=fa(v)){\r\n puts(\"-1\");\r\n continue;\r\n }\r\n printf(\"%d\\n\",lca(u,v));\r\n }\r\n}\r\n\r\nint main(){\r\n init();\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u9053\u6700\u5927\u751f\u6210\u6811\u52a0LCA\u7684\u88f8\u9898\u3002 \u56e0\u4e3a\u662f\u6c42\u8def\u4e0a\u6743\u503c\u6700\u5c0f\u7684\u8fb9\u6743\u503c\u6700\u5927\uff0c\u6240\u4ee5\u53ef\u4ee5\u5728\u6700\u5927\u751f\u6210\u6811\u4e0a\u8dd1\u3002\u5f53\u7136\u4e8c\u5206\u7b54\u6848\u52a001 … <\/p>\n