在下覺得這是一道很鬼畜的神題，因為在下第一眼覺得要用整體二分做。

雖然在下已經知道它是Kruskal+lca了，還是仍不住想試著用整體二分，然后寫了一個自認為十分好看的優秀代碼，十分優秀的T了。。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<vector> typedef long long LL; using namespace std; const int maxn=15000+299; const int maxm=30000*2+299; const int maxk=20000+299; int upp=0,n,m,k,ecnt,fir[maxn],nxt[maxm],to[maxm],val[maxm],vis[maxn]; struct node {int x,y,id,ans; }p[maxk],tp[maxk]; void add(int u,int v,int w) {nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w; } bool cmp(node x,node y) {return x.id<y.id; } queue<int>que; void bfs(int s,int lim) {que.push(s); vis[s]=s;while(!que.empty()) {int x=que.front();que.pop();for(int i=fir[x];i;i=nxt[i]) if(val[i]<=lim&&vis[to[i]]!=s) {vis[to[i]]=s;que.push(to[i]); }} } void solve(int l,int r,int ql,int qr) {if(ql>qr||l>r) return; int mid=(ql+qr)>>1;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) if(!vis[i]) bfs(i,mid);int lt=l,rt=r;for(int i=l;i<=r;i++) {if(vis[p[i].x]==vis[p[i].y]) {p[i].ans=mid; tp[lt++]=p[i];}else tp[rt--]=p[i];}for(int i=l;i<=r;i++) p[i]=tp[i];solve(l,lt-1,ql,mid-1); solve(lt,r,mid+1,qr); } int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);upp=max(upp,z);}for(int i=1;i<=k;i++) {scanf("%d%d",&p[i].x,&p[i].y);p[i].id=i; p[i].ans=-1;}solve(1,k,1,upp);sort(p+1,p+k+1,cmp);for(int i=1;i<=k;i++) {printf("%d\n",p[i].ans);}return 0; } View Code

然后正解，沒什么想說的，反正我十分難受。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<vector> typedef long long LL; using namespace std; const int maxn=15000+299; const int maxm=30000*2+299; const int maxk=20000+299; int upp=0,tot,n,m,k,ecnt,fir[maxn],nxt[maxm],to[maxm],val[maxm],vis[maxn],fa[maxn]; int f[maxn][32],st[maxn][32],R[maxn]; struct edge{int u,v,w;friend bool operator <(const edge&A,const edge&B) {return A.w<B.w;} }e[maxm]; void add(int u,int v,int w) {nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w; } void init() {scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); } int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);} void kruskal() {sort(e+1,e+m+1);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++) {int u=e[i].u,v=e[i].v;int fu=find(u),fv=find(v);if(fu!=fv) {add(u,v,e[i].w);tot++;if(tot==n-1) break;fa[fu]=fv;}} } void dfs(int x,int ff) {f[x][0]=ff; R[x]=R[ff]+1;for(int i=fir[x];i;i=nxt[i]) if(to[i]!=ff){st[to[i]][0]=val[i];dfs(to[i],x);} } void make_st() {for(int i=1;i<=30;i++)for(int j=1;j<=n;j++) {f[j][i]=f[f[j][i-1]][i-1];st[j][i]=max(st[j][i-1],st[f[j][i-1]][i-1]); } } int lca(int x,int y) {int res=0;if(R[x]<R[y]) swap(x,y);for(int i=30;i>=0;i--) {if(R[f[x][i]]>=R[y]) { res=max(res,st[x][i]);x=f[x][i]; }}if(x==y) return res;for(int i=30;i>=0;i--) {if(f[x][i]!=f[y][i]) {res=max(res,st[x][i]);res=max(res,st[y][i]);x=f[x][i]; y=f[y][i];}}res=max(res,st[x][0]);res=max(res,st[y][0]);return res; } void work() {for(int i=1;i<=k;i++) {int x,y;scanf("%d %d",&x,&y);printf("%d\n",lca(x,y));} } int main() {init();kruskal();dfs(1,0);make_st();work();return 0; } View Code

?

轉載于:https://www.cnblogs.com/Achenchen/p/7554475.html

總結

以上是生活随笔為你收集整理的BZOJ 3732 Network的全部內容，希望文章能夠幫你解決所遇到的問題。

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