我是靠谱客的博主 含蓄泥猴桃,最近开发中收集的这篇文章主要介绍圆方树、仙人掌,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

一、仙人掌的最大独立集(就是拆分为多棵基环树来做的):
注意:使用Tarjan算法时,注意题目要求需不需要处理重边。
在这里插入图片描述

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
//#define lc (p<<1)
//#define rc (p<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=120100;
int head[maxn],ver[maxn],nt[maxn];
int dfn[maxn],low[maxn],fa[maxn];
int dp[maxn][2],tot=1,cnt=0,n,m;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void toDp(int x,int y)
{
    int t0,t1,f0=0,f1=0;
    for(int i=y;i!=x;i=fa[i])
    {
        t0=f0+dp[i][0];//当前这个不选
        t1=f1+dp[i][1];//当前这个选
        f0=max(t0,t1);//当前这个点随意能到达的最大值
        f1=t0;//当前这个点不选的最大值
    }
    dp[x][0]+=f0;

    f0=0,f1=-inf;
    for(int i=y;i!=x;i=fa[i])
    {
        t0=f0+dp[i][0];
        t1=f1+dp[i][1];
        f0=max(t0,t1);
        f1=t0;
    }
    dp[x][1]+=f1;
}

void dfs(int x,int ff)
{
    fa[x]=ff;
    dfn[x]=low[x]=++cnt;
    dp[x][0]=0,dp[x][1]=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            dfs(y,x);
            low[x]=min(low[x],low[y]);
        }
        else if(y!=ff)low[x]=min(low[x],dfn[y]);//不用考虑重边
        if(low[y]>dfn[x])
        {
            dp[x][0]+=max(dp[y][0],dp[y][1]);
            dp[x][1]+=dp[y][0];
        }
    }
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(fa[y]!=x&&dfn[y]>dfn[x])//找到环上的非树边
            toDp(x,y);
    }
}

int main(void)
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    //图中无重边和自环
    dfs(1,0);
    printf("%dn",max(dp[1][0],dp[1][1]));
    return 0;
}

二、仙人掌的直径(就是拆分为多棵基环树来做的):
仙人掌的直径:两点之间最短路径最大值。
在这里插入图片描述
在这里插入图片描述

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
//#define lc (p<<1)
//#define rc (p<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=50100;
const int maxx=10000100;
int head[maxn],ver[maxx<<1],nt[maxx<<1];
int dfn[maxn],low[maxn],fa[maxn],d[maxn];
int dp[maxn],tot=1,cnt=0,n,m;
int q1[maxn<<1],q2[maxn<<1];
int ans=0;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void toDp(int x,int y)
{
    int t=0;
    for(int i=y;i!=x;i=fa[i])
        q1[++t]=i;
    q1[++t]=x;
    for(int i=1;i<=t;i++)
        q1[i+t]=q1[i];

    int l=1,r=0;
    for(int i=1;i<=t*2;i++)
    {
        while(l<=r&&i-q2[l]>t/2) l++;
        if(l<=r) ans=max(ans,dp[q1[i]]+dp[q1[q2[l]]]+i-q2[l]);
        while(l<=r&&dp[q1[i]]-i>=dp[q1[q2[r]]]-q2[r]) r--;
        q2[++r]=i;
    }
    for(int i=y;i!=x;i=fa[i])
        dp[x]=max(dp[x],dp[i]+min(d[i]-d[x],d[y]-d[i]+1));
}

void dfs(int x,int ff)
{
    fa[x]=ff;
    dfn[x]=low[x]=++cnt;
    d[x]=d[ff]+1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            dfs(y,x);
            low[x]=min(low[x],low[y]);
        }
        else if(y!=ff)low[x]=min(low[x],dfn[y]);//不考虑重边的问题
        if(low[y]>dfn[x])
        {
            ans=max(ans,dp[x]+dp[y]+1);
            dp[x]=max(dp[x],dp[y]+1);
        }
    }
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(fa[y]!=x&&dfn[y]>dfn[x])//找到环上的非树边
            toDp(x,y);
    }
}

void init(int n)
{
    for(int i=1;i<=n;i++)
        head[i]=dp[i]=dfn[i]=0;
    ans=0;
    tot=1;
    cnt=0;
}

int main(void)
{

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init(n);
        int k,x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&k,&x);
            for(int j=1;j<k;j++)
            {
                scanf("%d",&y);
                add(x,y);
                add(y,x);
                x=y;
            }
        }
        //图中无重边和自环
        dfs(1,0);
        printf("%dn",ans);
    }

    return 0;
}

三、最短路:仙人掌两点之间的最短路,还是要把仙人掌分开成多个基环树。
在这里插入图片描述

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#define ll long long
#define pr make_pair
#define pb push_back
//#define lc (p<<1)
//#define rc (p<<1|1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e15;
const int mod=1e9+7;
const int maxn=100100;
int dfn[maxn],low[maxn],fa[maxn],sum[maxn],val[maxn];
int cnt=0,n,m,q,cntf;
int f[maxn][20],t,d[maxn],dis[maxn];

struct Tree
{
    int head[maxn],ver[maxn],edge[maxn],nt[maxn];
    int tot=1;
    void add(int x,int y,int z)
    {
        ver[++tot]=y,edge[tot]=z;
        nt[tot]=head[x],head[x]=tot;
    }
}yy,yf;

void toBuild(int x,int y,int z)
{
    cntf++;
    sum[y]=z;
    for(int i=y;i!=x;i=fa[i])
        sum[fa[i]]=sum[i]+val[i];
    sum[cntf]=sum[x];
    sum[x]=0;

    for(int i=y;i!=fa[x];i=fa[i])
    {
        int minn=min(sum[i],sum[cntf]-sum[i]);
        yf.add(cntf,i,minn);
        yf.add(i,cntf,minn);
    }
}


void dfs(int x,int ff,int zz)
{
    fa[x]=ff,val[x]=zz;
    dfn[x]=low[x]=++cnt;

    for(int i=yy.head[x];i;i=yy.nt[i])
    {
        int y=yy.ver[i],z=yy.edge[i];
        if(!dfn[y])
        {
            dfs(y,x,z);
            low[x]=min(low[x],low[y]);
        }
        else if(y!=ff)low[x]=min(low[x],dfn[y]);//不考虑重边的问题

        if(low[y]>dfn[x])
        {
            yf.add(x,y,z);
            yf.add(y,x,z);
        }
    }

    for(int i=yy.head[x];i;i=yy.nt[i])
    {
        int y=yy.ver[i];
        if(fa[y]!=x&&dfn[y]>dfn[x])//找到环上的非树边
            toBuild(x,y,yy.edge[i]);
    }
}

void dfs(int x,int fa)
{
    for(int i=yf.head[x];i;i=yf.nt[i])
    {
        int y=yf.ver[i],z=yf.edge[i];
        if(y==fa) continue;
        d[y]=d[x]+1;
        dis[y]=dis[x]+z;
        f[y][0]=x;
        for(int j=1;j<=t;j++)
            f[y][j]=f[f[y][j-1]][j-1];
        dfs(y,x);
    }
}

int ask(int x,int y)
{
    int lca=0;

    if(d[x]>d[y]) swap(x,y);
    int nx=x,ny=y;
    for(int i=t;i>=0;i--)
        if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(x==y) lca=x;
    else
    {
        for(int i=t;i>=0;i--)
            if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
        lca=f[x][0];
    }
    if(lca<=n) return dis[nx]+dis[ny]-2*dis[lca];
    else return dis[nx]+dis[ny]-dis[x]-dis[y]+min(abs(sum[x]-sum[y]),sum[lca]-abs(sum[x]-sum[y]));
}

int main(void)
{

    scanf("%d%d%d",&n,&m,&q);
    cntf=n;//方点编号
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        yy.add(x,y,z);
        yy.add(y,x,z);
    }
    dfs(1,0,0);

    t=log2(cntf)+1;
    d[0]=-1;
    dfs(1,0);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%dn",ask(x,y));
    }

    return 0;
}


最后

以上就是含蓄泥猴桃为你收集整理的圆方树、仙人掌的全部内容,希望文章能够帮你解决圆方树、仙人掌所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(38)

评论列表共有 0 条评论

立即
投稿
返回
顶部