概述
一、仙人掌的最大独立集(就是拆分为多棵基环树来做的):
注意:使用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;
}
最后
以上就是含蓄泥猴桃为你收集整理的圆方树、仙人掌的全部内容,希望文章能够帮你解决圆方树、仙人掌所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复