[51nod]1743 雪之国度【Kruskal+LCA+双连通分量】

1743 雪之国度

【题目描述】

传送门

【题解】

这解法十分神奇,是一道不错的小题。
我们有个贪心的想法,从小的开始加边,知道x->y满足双连通分量为止,那么最小生成树上的边肯定是要取的,所以可以预先Kruskal处理出一棵最小生成树,然后加入非树边,使之构成双连通分量。

最小生成树上的边一定不会是答案,这个好证:
如果答案是最小生成树上的边,那么之后加入的非树边一定小于这条边,那么在Kruskal时肯定先枚举到这些非树边,并且这些非树边可以使这条边两端连通,所以说Kruskal选择的树边应是这些非树边,而不会选这条边。

那么最小生成树上的边权对答案是没有贡献的,我们只要看这些非树边就可以了。
对于每一条非树边(x,y),这条非树边可以使树上x->y这条路径变成双连通分量,所以我们就可以用这个值更新x->y这条路径。

非树边肯定要从小的开始枚举,如果x->y这条路径上的路径p->q已经更新过了,那么就不用再次更新了,因为已经从小到大枚举非树边更新了,所以就可以用并查集跳过这一段。
然后对于每次询问,LCA求解就可以了。

无解的情况也就是x->y没有被更新过,所以判一下并查集就可以了。

思路十分清晰,代码也很好写。

代码如下

#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define MAXN 100005
#define MAXE 500005
using namespace std;
int n,m,q,a[MAXN],Fa[MAXN],Dep[MAXN],F[MAXN][20],S[MAXN][20];
bool vis[MAXE];
struct Edge{
    int tot,lnk[MAXN],son[MAXE<<1],nxt[MAXN<<1];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}T;
struct xcw{
    int x,y,w;
    bool operator <(const xcw b)const{return w<b.w;}
}E[MAXE];
int _abs(int x){return x<0?-x:x;}
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
int get(int x){return Fa[x]==x?x:Fa[x]=get(Fa[x]);}
void Kruskal(){
    sort(E+1,E+1+m);
    for(int i=1;i<=n;i++) Fa[i]=i;
    for(int i=1;i<=m;i++){
        int fx=get(E[i].x),fy=get(E[i].y);
        if(fx==fy) continue;
        Fa[fy]=fx,vis[i]=1;
        T.Add(E[i].x,E[i].y),T.Add(E[i].y,E[i].x);
    }
}
void DFS(int x,int fa){
    Dep[x]=Dep[fa]+1;F[x][0]=fa;
    for(int j=T.lnk[x];j;j=T.nxt[j]) if(T.son[j]!=fa) DFS(T.son[j],x);
}
void Pre(){
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1,x;i<=n;i++) F[i][j]=F[x=F[i][j-1]][j-1],S[i][j]=max(S[i][j-1],S[x][j-1]);
}
int LCA(int x,int y){
    if(Dep[x]<Dep[y]) swap(x,y);
    int Del=Dep[x]-Dep[y],Sum=0;
    for(int j=0;(1<<j)<=Del;j++) if(Del&(1<<j)) Sum=max(Sum,S[x][j]),x=F[x][j];
    if(x==y) return Sum;
    for(int j=log2(n);j>=0;j--)
    if(F[x][j]!=F[y][j]) Sum=max(Sum,max(S[x][j],S[y][j])),x=F[x][j],y=F[y][j];
    Sum=max(Sum,max(S[x][0],S[y][0]));
    return Sum;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),m=read();q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1,x,y;i<=m;i++) E[i]=(xcw){x=read(),y=read(),_abs(a[x]-a[y])};
    Kruskal();DFS(1,0);
    for(int i=1;i<=n;i++) Fa[i]=i;
    for(int i=1;i<=m;i++)
    if(!vis[i]){
        int x=get(E[i].x),y=get(E[i].y);
        while(x!=y){
            if(Dep[x]<Dep[y]) swap(x,y);
            S[x][0]=E[i].w,Fa[x]=F[x][0],x=get(x);
        }
    }
    Pre();
    for(int i=1;i<=q;i++){
        int x=read(),y=read();
        if(get(x)!=get(y)) printf("infinitely\n");
        else printf("%d\n",LCA(x,y));
    }
    return 0;
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部