Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

[51nod1743]雪之国度

Description
雪之国度有N座城市,依次编号为1到N,又有M条道路连接了其中的城市,每一条道路都连接了不同的2个城市,任何两座不同的城市之间可能不止一条道路。
雪之女王赋予了每一座城市不同的能量,其中第i座城市被赋予的能量为Wi
如果城市u和v之间有一条道路,那么只要此刻雪之女王的能量不小于|Wu - Wv|,这条道路就是安全的。
如果城市u和v之间存在两条没有重复道路的安全路径(其中每一段道路都是安全的),则认为这两座城市之间有着良好的贸易关系。
最近,雪之女王因为情感问题,她的能量产生巨大的波动。为了维持雪之国度的经济贸易,她希望你能帮忙对Q对城市进行调查。
对于第j对城市u_jv_j,她希望知道在保证这两座城市之间有着良好贸易关系的前提之下,自己最少需要保持多少的能量。

Input
每一组数据第一行有3个整数,依次为N,M,Q,表示城市个数,道路个数,和所需要进行的调查次数。
之后一行,有N个整数,依次为每一个城市被赋予的能量Wi
之后M行,每一行有2个整数,表示对应编号的两个城市之间有一条道路。
之后Q行,每一行有2个整数,表示一组调查的城市目标。

对于100%的数据来说,3<=N<=100000, 3<=M<=500000, 1<=Q<=100000, 每一座城市的能量Wi满足0<=Wi<=200000

Output
输出一共有Q行,依次对应Q次调查的结果。
其中第j行给出了第j次调查的结果,即雪之女王需要保持的最少能量值。如果永远也无法做到,输出”infinitely“。

Solution
先建出Kruskal生成树,对于这上面的边显然没用,然后将剩下的边从小到大加入,用倍增更新树边上的值,由于从小到大加入树,对于之前更新过的边就不需要更新,使用并查集来判断。
处理完后在倍增处理LCA和边权最大值即可。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define V 100005
#define E 500005
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}


int N,M,Q,W[V],x,y,F[20][V],G[20][V],Fa[V],vis[E],Dep[V];
int head[V],nxt[E<<1],to[E<<1],w[E<<1],Cnt;
#define Add(x,y,c) (nxt[++Cnt]=head[x],to[Cnt]=y,w[Cnt]=c,head[x]=Cnt)

struct Edge{int x,y,c;}tr[E];
int Cmp(Edge x,Edge y){return x.c<y.c;}
void dfs(int x,int fa){F[0][x]=fa,Dep[x]=Dep[fa]+1;for(int i=head[x];i;i=nxt[i])if(to[i]^fa)dfs(to[i],x);}
int getf(int x){return x==Fa[x]?x:Fa[x]=getf(Fa[x]);}
void Kruskal(void){
    sort(tr+1,tr+M+1,Cmp);
    for(int i=1;i<=N;i++)Fa[i]=i;
    for(int i=1;i<=M;i++){
        int x=getf(tr[i].x),y=getf(tr[i].y);
        if(x^y)vis[i]=1,Add(tr[i].x,tr[i].y,tr[i].c),Add(tr[i].y,tr[i].x,tr[i].c),Fa[x]=y;
    }
}

void init(void){
    for(int i=1;(1<<i)<=N;i++)
        for(int j=1;j<=N;j++)
            F[i][j]=F[i-1][F[i-1][j]],G[i][j]=max(G[i-1][j],G[i-1][F[i-1][j]]);
}
int LCA(int x,int y){
    int Sum=0;
    if(Dep[x]<Dep[y])swap(x,y);
    for(int i=17;~i;i--)if(Dep[F[i][x]]>=Dep[y])Sum=max(Sum,G[i][x]),x=F[i][x];
    if(x==y)return Sum;
    for(int i=17;~i;i--)if(F[i][x]^F[i][y])
        Sum=max(Sum,max(G[i][x],G[i][y])),x=F[i][x],y=F[i][y];
    Sum=max(Sum,max(G[0][x],G[0][y]));
    return Sum;
}

int main()
{
    read(N),read(M),read(Q);
    for(int i=1;i<=N;i++)read(W[i]);
    for(int i=1;i<=M;i++)read(tr[i].x),read(tr[i].y),tr[i].c=abs(W[tr[i].x]-W[tr[i].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]){
        x=getf(tr[i].x),y=getf(tr[i].y);
        while(x^y){
            if(Dep[x]<Dep[y])swap(x,y);
            G[0][x]=tr[i].c,Fa[x]=F[0][x],x=getf(x);
        }
    }
    init();
    for(int i=1;i<=Q;i++){
        read(x),read(y);
        if(getf(x)^getf(y))puts("infinitely");
        else printf("%d\n",LCA(x,y));
    }
}
Share this Post

Leave a Comment

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*