ZOJ 3649 Social Net:最大生成树+树上倍增 DP


题目链接:ZOJ 3649 Social Net

Problem

There are n individuals (2 <= n <= 30000). Everyone has one or more friends. And everyone can contact all people by friend-relation. If two persons aren't friends, they also can contact by their friends. Each pair of friends have a friendship value a_i (1 <= a_i <= 50000).
Firstly, you will relieve some friend-relation. The rest of the friend-relation is the social net. The net is unique in all test cases. In this net, everyone can contact all people by rest friend-relation. The net has a minimum number of friend-relation. And the net has maximum sum of friendship value. We want to get the maximum sum.
Secondly, everyone has an angry value bi (1 <= b_i <= 100000). We have q operations (1 <= q <= 30000): Person X wants to contact person Y, this operation merely has one sequence which describes the process. The sequence consists of persons' angry value. The persons are on the process.
We suppose the sequence is c_1, c_2, c_3, ... ,c_i. Here c_i means the angry value of the ith people in the sequence.
We attempt to find the maximum c_k-c_j (c_k >= c_j, j <= k).

Example:
The sequence is 3(X), 4, 5, 6, 7, 5, 9, 4, 11(Y). The maximum c_k-c_j is 11-3=8.
The sequence is 3(X), 4, 5, 6, 7, 5, 9, 2, 11(Y). The maximum c_k-c_j is 11-2=9.
The sequence is 3(X), 10, 2, 5(Y). The maximum c_k-c_j is 10-3=7.

Input

The input contains multiple test cases. Each test case begins with a line containing a single integer n. The following line contains n integers b_i.
The subsequent line describe the number of relations m (n <= m <= 50000). The next m lines contain the information about relations: x, y, a_i. Their friendship value is a_i.
Afterward gives q. The next q lines contain the operations: x, y. person X wants to contact person Y.

Output

For each case, print maximum sum of friendship value of the net on the first line.
The next q lines contain the answers of every operations.

Sample Input

6
3 5 1 7 3 5
7
1 2 5
1 3 6
2 4 7
2 5 8
3 6 9
4 5 1
5 6 2
5
6 1
6 2
6 3
6 4
6 5

Sample Output

35
2
4
0
6
4

Translation

题目意思抽象出来是:给你 n 个点的一张图,先求最大生成树,然后在树里给出一大堆询问,对于每对询问给出两个参数 x_i,y_i,问你树上这两点之间最短路上 w(j)-w(i) 的最大值,其中要保证 i <= j

Analysis

第一问求最大生成树果断的 Kruskal,不用讲了……

第二问,如果直接问我们路径上 w(j)-w(i) 的最大值,很显然可以用树上倍增解决,但是麻烦之处就在于这个 i \le j。这可怎么办呢?

我们可以用一个分治的思想:如果把 XY 的路径看成一个数列,那么我们可以从中间割开,左右分别处理出答案,然后最终答案就是这个数列里右边的最大值和左边的最小值之差,和左右答案取个 max。

那么我们自然想到了:维护五个树上倍增数组:

  • F(i,j) 表示从 i 点向上推 2^j 个单位的点;

  • max_num(i,j) 表示从 i 点向上推 2^j 个单位的距离内 w(i) 的最大值;

  • min_num(i,j) 表示从 i 点向上推 2^j 个单位的距离内 w(i) 的最小值;

  • dif_upd(i,j) 表示从 i 点向上推 2^j 个单位的距离内的差值最大值;

  • dif_dwn(i,j) 表示从 i 点向上推 2^j 个单位的距离内的反向差值最大值;

什么叫“反向差值”呢?根据 i \le j,“正向差值”是指对于 i \le j 的差值,“反向差值” 则是对于 j \le i 的差值。

其实思路清晰,写起来并不算麻烦。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30005,maxm=60005,maxe=50005;
int n,m,q,w[maxn],fa[maxn],deep[maxn],sum=0;
int tot=0,lnk[maxn],nxt[maxm],son[maxm];
int f[maxn][20],max_num[maxn][20],min_num[maxn][20],dif_upd[maxn][20],dif_dwn[maxn][20];
bool vis[maxn];
struct Edge{
    int x,y,w;
}e[maxe];
inline int max3(int x,int y,int z){
    return z>max(x,y)?z:max(x,y);
}
inline bool Compare(Edge a,Edge b){
    return a.w>b.w;
}
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline int Abs(int x){
    return x<0?-x:x;
}
inline void add(int x,int y){
    tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void Init(){
    memset(w,0,sizeof(w));
    memset(fa,0,sizeof(fa));
    memset(deep,0,sizeof(deep));
    memset(f,0,sizeof(f));
    memset(max_num,0,sizeof(max_num));
    memset(min_num,0,sizeof(min_num));
    memset(dif_upd,0,sizeof(dif_upd));
    memset(dif_dwn,0,sizeof(dif_dwn));
    tot=0;sum=0;
    memset(lnk,0,sizeof(lnk));
    memset(nxt,0,sizeof(nxt));
    memset(son,0,sizeof(son));
    memset(vis,0,sizeof(vis));
    memset(e,0,sizeof(e));
}
inline int getfa(int x){
    if (fa[x]==x) return x;
    fa[x]=getfa(fa[x]);
    return fa[x];
}
inline void Kruskal(){
    sort(e+1,e+1+m,Compare);
    for (int i=1;i<=n;i++) fa[i]=i;
    int cnt=0;
    for (int i=1;i<=m&&cnt<n-1;i++){
        int fx=getfa(e[i].x),fy=getfa(e[i].y);
        if (fx==fy) continue;
        sum+=e[i].w;
        add(e[i].x,e[i].y);add(e[i].y,e[i].x);
        fa[fx]=fy;cnt++;
    }
    if (cnt!=n-1) printf("ERROR!!!!!\n");
}
inline void BuildTree(int x){
    vis[x]=1;
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        fa[son[i]]=x;
        deep[son[i]]=deep[x]+1;
        BuildTree(son[i]);
    }
}
inline void Build(){
    for (int i=1;i<=n;i++){
        f[i][0]=fa[i];
        max_num[i][0]=max(w[i],w[fa[i]]);
        min_num[i][0]=min(w[i],w[fa[i]]);
        dif_upd[i][0]=w[fa[i]]-w[i];dif_dwn[i][0]=w[i]-w[fa[i]];
    }
    for (int j=1;j<20;j++)
        for (int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            max_num[i][j]=max(max_num[i][j-1],max_num[f[i][j-1]][j-1]);
            min_num[i][j]=min(min_num[i][j-1],min_num[f[i][j-1]][j-1]);
            dif_upd[i][j]=max3(dif_upd[i][j-1],dif_upd[f[i][j-1]][j-1],max_num[f[i][j-1]][j-1]-min_num[i][j-1]);
            dif_dwn[i][j]=max3(dif_dwn[i][j-1],dif_dwn[f[i][j-1]][j-1],max_num[i][j-1]-min_num[f[i][j-1]][j-1]);
        }
    // for (int i=1;i<=n;i++){
    //     printf("I=%d -------------\n",i);
    //     for (int j=0;j<19;j++) printf("%d ",f[i][j]);printf("\n");
    //     printf("MAX_NUM: ");for (int j=0;j<19;j++) printf("%d ",max_num[i][j]);printf("\n");
    //     printf("MIN_NUM: ");for (int j=0;j<19;j++) printf("%d ",min_num[i][j]);printf("\n");
    //     printf("DIF_UPD: ");for (int j=0;j<19;j++) printf("%d ",dif_upd[i][j]);printf("\n");
    //     printf("DIF_DWN: ");for (int j=0;j<19;j++) printf("%d ",dif_dwn[i][j]);printf("\n");
    //     printf("\n");
    // }
}
inline int GetAnswer(int x,int y){
    int ret=0;
    int now_min=1e8,now_max=0;
    if (x==y) return 0;
    for (int i=19;i>=0;i--) if (deep[f[x][i]]>=deep[y]){
        ret=max3(ret, max_num[x][i]-now_min, dif_upd[x][i]);
        now_min=min(now_min,min_num[x][i]);
        x=f[x][i];
    }
    for (int i=19;i>=0;i--) if (deep[f[y][i]]>=deep[x]){
        ret=max3(ret, now_max-min_num[y][i], dif_dwn[y][i]);
        now_max=max(now_max,max_num[y][i]);
        y=f[y][i];
    }
    if (x==y) return ret;
    for (int i=19;i>=0;i--) if (f[x][i]!=f[y][i]){
        ret=max3(ret,dif_upd[x][i],dif_dwn[y][i]);
        ret=max3(ret,max_num[x][i]-now_min,now_max-min_num[y][i]);
        now_min=min(now_min,min_num[x][i]);
        now_max=max(now_max,max_num[y][i]);
        x=f[x][i];y=f[y][i];
    }
    ret=max3(ret,dif_upd[x][0],dif_dwn[y][0]);
    ret=max3(ret,max_num[x][0]-now_min,now_max-min_num[y][0]);
    now_min=min(now_min,min_num[x][0]);
    now_max=max(now_max,max_num[y][0]);
    ret=max(ret,now_max-now_min);
    return ret;
}
int main(){
    while (scanf("%d",&n)!=-1){
        Init();
        for (int i=1;i<=n;i++) w[i]=read(),fa[i]=i;
        m=read();
        for (int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].w=read();
        Kruskal();printf("%d\n",sum);

        memset(fa,0,sizeof(fa));
        deep[1]=1;BuildTree(1);
        //printf("Deep:");for (int i=1;i<=n;i++) printf("%d ",deep[i]);printf("\n");
        //for (int i=1;i<=n;i++) printf("fa[%d]=%d\n",i,fa[i]);printf("\n");

        Build();
        q=read();
        for (int i=1;i<=q;i++){
            int x=read(),y=read();
            printf("%d\n",GetAnswer(x,y));
        }
    }
    return 0;
}

本文采用 BY-NC-SA 3.0 协议进行授权。

欢迎转载,如有错误欢迎指出。

本文链接:https://skywt.cn/posts/zoj3649/


我们的征途是星辰大海。