欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

jzoj5844 c 倍增

程序员文章站 2024-02-12 22:46:22
...

Description


给定一个无向连通图,n 个点(下标从 1 开始),m 条边,每条边有一个颜色。保证无自环,没有长度超过 2 的简单环。
现有 q 个询问:给出两个点 x、y,选择一条 x 到 y 简单路径(不经过重复的点),经过的边将形成一个颜色序列,价值为相同颜色的极大连续段个数,求出最大的价值。
jzoj5844 c 倍增

Solution


人均3k码量,鸣谢LZH犇给的的对拍
一开始就看错题意了,以为是最长的颜色连续长度,然鹅是最多的段数

考虑树形图要怎么做。由于每一条树边唯一对应一个边权,直接倍增/树剖统计就行了
这非常有启发性。注意到一条链上的边最多与两条链相邻,因此我们只需要记录一条边上的三种不同权值。用r[x][i][s1][s2]表示从x出发向上2^i层后,最顶端和最底端两条边的权编号为s1、s2时的最大分段数

这道题口胡非常容易,写起来细节比较多(我比较菜
比如我们可以把边权下放给儿子,用down[x][i]记录x向上2^i层后链上倒数第二个节点,这样可以比较方便地求出顶端和底端的链的权
比如dfs的时候要考虑出现沿着很多个小环走成大环的情况
写出来很有成就感

Code


#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define copy(x,t) memcpy(x,t,sizeof(x))
#define fill(x,t) memset(x,t,sizeof(x))

const int N=300005;
const int E=600005;

std:: map <int,bool> map[N];

struct edge {int y,w,next;} e[E];

int fa[N][18],r[N][18][4][4],dep[N],down[N][18];
int wjp[4][4],tmp1[4][4],tmp2[4][4],ret[4][4],c[N][4];
int ls[N],edCnt;

bool vis[N];

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

void add_edge(int x,int y,int w) {
    e[++edCnt]=(edge) {y,w,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge) {x,w,ls[y]}; ls[y]=edCnt;
}

void dfs1(int now) {
    rep(i,1,17) fa[now][i]=fa[fa[now][i-1]][i-1];
    rep(i,1,17) down[now][i]=down[fa[now][i-1]][i-1];
    vis[now]=true;
    for (int i=ls[now];i;i=e[i].next) {
        if (vis[e[i].y]) continue;
        dep[e[i].y]=dep[now]+1; fa[e[i].y][0]=now;
        down[e[i].y][0]=e[i].y;
        dfs1(e[i].y);
    }
}

void work(int now) {
    rep(i,1,17) {
        rep(c1,1,c[now][0]) rep(c2,1,c[down[now][i-1]][0]) {
            rep(c3,1,c[fa[now][i-1]][0]) rep(c4,1,c[down[now][i]][0]) {
                r[now][i][c1][c4]=std:: max(r[now][i][c1][c4],r[now][i-1][c1][c2]+r[fa[now][i-1]][i-1][c3][c4]-(c[down[now][i-1]][c2]==c[fa[now][i-1]][c3]));
            }
        }
    }
    for (int i=ls[now];i;i=e[i].next) {
        if (dep[e[i].y]<=dep[now]) continue;
        if (c[e[i].y][0]==3) continue;
        bool flag=true;
        rep(j,1,c[e[i].y][0]) {
            if (c[e[i].y][j]==e[i].w) {
                flag=false; break;
            }
        }
        if (flag) c[e[i].y][++c[e[i].y][0]]=e[i].w;
    }
    for (int i=ls[now];i;i=e[i].next) {
        if (dep[e[i].y]<=dep[now]) continue;
        rep(j,1,c[e[i].y][0]) {
            r[e[i].y][0][j][j]=1;
        }
    }
}

void dfs2(int now) { vis[now]=true;
    work(now);
    for (int i=ls[now];i;i=e[i].next) {
        if (vis[e[i].y]) continue;
        dfs2(e[i].y);
    }
}

int get_lca(int x,int y) {
    if (dep[x]<dep[y]) std:: swap(x,y);
    drp(i,17,0) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if (x==y) return x;
    drp(i,17,0) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int get_up(int x,int up) {
    fill(ret,0); int last=x,st=x;
    bool first=true;
    drp(i,17,0) {
        if (dep[fa[x][i]]>=dep[up]) {
            fill(wjp,0);
            if (first) {
                copy(wjp,r[x][i]);
                first=false;
            } else {
                rep(c1,1,c[st][0]) rep(c2,1,c[last][0]) {
                    rep(c3,1,c[x][0]) rep(c4,1,c[down[x][i]][0]) {
                        wjp[c1][c4]=std:: max(wjp[c1][c4],ret[c1][c2]+r[x][i][c3][c4]-(c[last][c2]==c[x][c3]));
                    }
                }
            }
            copy(ret,wjp); last=down[x][i]; x=fa[x][i];
        }
    }
    return last;
}

void solve(int x,int y) {
    int lca=get_lca(x,y),ans=0,ux,uy;
    if (x==lca) {
        uy=get_up(y,lca); copy(tmp2,ret);
        rep(c1,1,c[y][0]) rep(c2,1,c[uy][0]) {
            ans=std:: max(ans,tmp2[c1][c2]);
        }
    } else if (y==lca) {
        ux=get_up(x,lca); copy(tmp1,ret);
        rep(c1,1,c[x][0]) rep(c2,1,c[ux][0]) {
            ans=std:: max(ans,tmp1[c1][c2]);
        }
    } else {
        ux=get_up(x,lca); copy(tmp1,ret);
        uy=get_up(y,lca); copy(tmp2,ret);
        rep(c1,1,c[x][0]) rep(c2,1,c[ux][0]) {
            rep(c3,1,c[y][0]) rep(c4,1,c[uy][0]) {
                ans=std:: max(ans,tmp1[c1][c2]+tmp2[c3][c4]-(c[ux][c2]==c[uy][c4]));
            }
        }
    }
    printf("%d\n", ans);
}

int main(void) {
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    int n=read(),m=read();
    rep(i,1,m) {
        int x=read(),y=read(),w=read();
        add_edge(x,y,w);
    }
    dep[1]=1; dfs1(1); fill(vis,0);
    dfs2(1);
    for (int T=read();T--;) {
        int x=read(),y=read();
        solve(x,y);
    }
    return 0;
}
相关标签: jzoj