【kruscal】【最小生成树】【块状树】bzoj3732 Network

浏览数：50 / 时间：2015年06月09日

跟去年NOIP某题基本一样。

最小生成树之后，就变成了询问连接两点的路径上的权值最大的边。

倍增LCA、链剖什么的随便搞。

块状树其实也是很简单的，只不过每个点的点权要记录成“连接其与其父节点的边的权值”，然后暴力LCA时不要用LCA的值更新答案了。

  1 #include<cmath>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define maxn 15001
  7 int Res,Num;char C,CH[20];
  8 inline int Ge()
  9 {
 10     Res=0;C=‘*‘; 
 11     while(C<‘0‘||C>‘9‘)C=getchar();
 12     while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}
 13     return Res;
 14 }
 15 inline void P(int x)
 16 {
 17     Num=0;if(!x){putchar(‘0‘);puts("");return;}
 18     while(x>0)CH[++Num]=x%10,x/=10;
 19     while(Num)putchar(CH[Num--]+48);
 20     putchar(‘\n‘);
 21 }
 22 struct Edge{int u,v,w;void Read(){u=Ge();v=Ge();w=Ge();}};
 23 bool cmp(const Edge &a,const Edge &b){return a.w<b.w;}
 24 Edge edges[maxn<<1];
 25 struct Graph
 26 {
 27     int v[maxn<<1],first[maxn<<1],next[maxn<<1],w[maxn<<1],en;
 28     void AddEdge(const int &a,const int &b)
 29     {v[++en]=b;next[en]=first[a];first[a]=en;}
 30     void AddEdge(const int &a,const int &b,const int &c)
 31     {v[++en]=b;w[en]=c;next[en]=first[a];first[a]=en;}
 32 };
 33 Graph G[2];
 34 int fa[maxn],dep[maxn],top[maxn],siz[maxn],sz,maxv[maxn],W[maxn];
 35 int n,m,q,x,y;
 36 void makeblock(int cur)
 37 {
 38     for(int i=G[0].first[cur];i;i=G[0].next[i])
 39       if(G[0].v[i]!=fa[cur])
 40         {
 41           dep[G[0].v[i]]=dep[cur]+1;
 42           W[G[0].v[i]]=G[0].w[i];
 43           fa[G[0].v[i]]=cur;
 44           if(siz[top[cur]]<sz)
 45             {
 46               siz[top[cur]]++;
 47               top[G[0].v[i]]=top[cur];
 48               G[1].AddEdge(cur,G[0].v[i]);
 49             }
 50           makeblock(G[0].v[i]);
 51         }
 52 }
 53 int rank[maxn],father[maxn];
 54 void init(){for(int i=1;i<=n;i++) father[i]=i;}
 55 int findroot(int x) 
 56 {
 57     if(father[x]==x) return x;
 58     int rt=findroot(father[x]);
 59     father[x]=rt;
 60     return rt;
 61 }
 62 void Union(int U,int V)
 63 {
 64     if(rank[U]<rank[V]) father[U]=V;
 65     else
 66       {
 67         father[V]=U;
 68         if(rank[U]==rank[V]) rank[U]++;
 69       }
 70 }
 71 void dfs(int cur,int Maxnow)
 72 {
 73     maxv[cur]=Maxnow;
 74     for(int i=G[1].first[cur];i;i=G[1].next[i])
 75       dfs(G[1].v[i],max(Maxnow,W[G[1].v[i]]));
 76 }
 77 int Query_max(int u,int v)
 78 {
 79     int res=-2147483647;
 80     while(u!=v)
 81       {
 82           if(top[u]==top[v])
 83             {
 84                 if(dep[u]<dep[v]) swap(u,v);
 85                 res=max(res,W[u]);
 86                 u=fa[u];
 87             }
 88           else
 89             {
 90                 if(dep[top[u]]<dep[top[v]]) swap(u,v);
 91                 res=max(res,maxv[u]);
 92                 u=fa[top[u]];
 93             }
 94       }
 95     return res;
 96 }
 97 int main()
 98 {
 99     n=Ge();m=Ge();q=Ge();
100     for(int i=1;i<=m;i++) edges[i].Read();
101     sort(edges+1,edges+m+1,cmp);
102     init();
103     int cnt=0;
104     for(int i=1;i<=m;i++)
105       {
106           int f1=findroot(edges[i].u),f2=findroot(edges[i].v);
107           if(f1!=f2)
108             {
109                 Union(f1,f2);
110                 G[0].AddEdge(edges[i].u,edges[i].v,edges[i].w);
111                 G[0].AddEdge(edges[i].v,edges[i].u,edges[i].w);
112                 cnt++;
113                 if(cnt==n-1) break;
114             }
115       }
116     sz=sqrt(n);
117     for(int i=1;i<=n;i++)
118       {
119           top[i]=i;
120           siz[i]=1;
121       }
122     makeblock(1);
123     for(int i=1;i<=n;i++) if(top[i]==i) dfs(i,W[i]);
124     for(int i=1;i<=q;i++) {x=Ge();y=Ge();P(Query_max(x,y));}
125     return 0;
126 }