圆方树

2024-01-08 08:15:10

当一张图每条边最多属于一个环的时候，这个图叫做仙人掌

圆方树用来解决仙人掌上的问题

1.仙人掌上最大独立集

仙人掌上做dp可以分成树边和环边两种边

所以相当于实现树形和环形dp

  void tarjan(ll x,ll y)
  {
    dfn[x]=low[x]=++cnt;
    for (ll u=head[x];u;u=e[u].a)
    {
        ll v=e[u].b;
        if (v==y) continue;
        if (!dfn[v])
        {
            fa[v]=x;
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
        } else low[x]=min(low[x],dfn[v]);
        if (low[v]>dfn[x]) {树形dp;} 
    }
    for (ll u=head[x];u;u=e[u].a)
    {
        ll v=e[u].b;
        if (fa[v]!=x&&dfn[v]>dfn[x]) 环形dp;
    }
  }

圆方树dp就套上面的板子就可以了

圆方树
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

//#include <immllrin.h>
//#include <emmllrin.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,h,t) for (ll i=h;i<=t;i++)
#define dep(i,t,h) for (ll i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define IL inline
#define rll register ll
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
char ss[1<<24],*A=ss,*B=ss;
IL char gc()
{
    return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void maxa(T &x,T y)
{
    if (y>x) x=y;
}
template<class T>void mina(T &x,T y)
{
    if (y<x) x=y;
}
template<class T>void read(T &x)
{
    ll f=1,c; while (c=gc(),c<48||c>57) if (c==‘-‘) f=-1; x=(c^48);
    while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f;
}
struct cp {
    ll x,y;
    cp operator +(cp B)
    {
        return (cp){x+B.x,y+B.y};
    }
    cp operator -(cp B)
    {
        return (cp){x-B.x,y-B.y};
    }
    ll operator *(cp B)
    {
        return x*B.y-y*B.x;
    }
    ll half() { return y < 0 || (y == 0 && x < 0); }
};
struct re{
    ll a,b,c;
};
const ll N=3e5;
ll n,m,q,f1,f2;
ll dfn[N],low[N],cnt,fa[N],f[N][2];
ll head[N],l;
re e[N*2];
void arr(ll x,ll y)
{
  e[++l].a=head[x];
  e[l].b=y;
  head[x]=l;
}
void solve(ll x,ll v)
{ 
  ll f0=0,f1=-1e9,t0,t1;
  for (ll i=v;i!=x;i=fa[i])
  {
      t0=f[i][0]+max(f0,f1);
      t1=f[i][1]+f0;
      f0=t0; f1=t1;
  }
  f[x][0]+=max(f0,f1);
  f0=-1e9,f1=0;
  for (ll i=v;i!=x;i=fa[i])
  {
      t0=f[i][0]+max(f0,f1);
      t1=f[i][1]+f0;
      f0=t0; f1=t1;
  }
  f[x][1]+=f0;
}
  void tarjan(ll x,ll y)
  {
    dfn[x]=low[x]=++cnt;
//    cerr<<x<<endl;
    f[x][0]=0; f[x][1]=1;
    for (ll u=head[x];u;u=e[u].a)
    {
        ll v=e[u].b;
        if (v==y) continue;
        if (!dfn[v])
        {
            fa[v]=x;
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
        } else low[x]=min(low[x],dfn[v]);
        if (low[v]>dfn[x]) {f[x][0]+=max(f[v][1],f[v][0]),f[x][1]+=f[v][0];} 
    }
    for (ll u=head[x];u;u=e[u].a)
    {
        ll v=e[u].b;
        if (fa[v]!=x&&dfn[v]>dfn[x]) solve(x,v);
    }
  }
int main()
{
   ios::sync_with_stdio(false);
   cin>>n>>m;
   rep(i,1,m)
   {
        ll u,v,w;
        cin>>u>>v;
        arr(u,v); arr(v,u);
   }  
   tarjan(1,0);
   cout<<max(f[1][0],f[1][1]);
   return 0;
}
View Code

2.Winter Festival

题目描述

Peter最喜欢的季节是冬天。为了庆祝冬天的活动，Peter准备装饰他所在的城市。

城市有许多区域，有一些道路连接着某些区域对。Peter想给每条道路装饰成数字0,1或2之一。

一组方案合法当且仅当满足以下两个条件：

  1. 对于任意两条不同的边(x, y), (x, z)，它们的边权和mod 3不等于1。

  2. 对于任意一个简单环，里面的所有边的边权和必须是奇数。

请找到一组合法方案，使得所有边的边权之和最小。(n,m<=100000)

 题解：

比较显然对于边权和mod 3不等于1这个条件 等价于不能同时出现0,1且不能出现两个2

于是如果这个是树我们可以记录f[x][i][j][k]表示当前在x点0/1/2有无出现

现在变成仙人掌多一个环形dp

代码好像写的比较麻烦

圆方树
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

//#include <immllrin.h>
//#include <emmllrin.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,h,t) for (ll i=h;i<=t;i++)
#define dep(i,t,h) for (ll i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define IL inline
#define rll register ll
#define me1(g) memset(g,1,sizeof(g))
#define mep(x,y) memcpy(x,y,sizeof(y))
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
char ss[1<<24],*A=ss,*B=ss;
IL char gc()
{
    return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void maxa(T &x,T y)
{
    if (y>x) x=y;
}
template<class T>void mina(T &x,T y)
{
    if (y<x) x=y;
}
template<class T>void read(T &x)
{
    ll f=1,c; while (c=gc(),c<48||c>57) if (c==‘-‘) f=-1; x=(c^48);
    while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f;
}
struct cp {
    ll x,y;
    cp operator +(cp B)
    {
        return (cp){x+B.x,y+B.y};
    }
    cp operator -(cp B)
    {
        return (cp){x-B.x,y-B.y};
    }
    ll operator *(cp B)
    {
        return x*B.y-y*B.x;
    }
    ll half() { return y < 0 || (y == 0 && x < 0); }
};
struct re{
    ll a,b,c;
};
const ll N=3e5;
ll n,m,q,f1,f2;
ll dfn[N],low[N],cnt,fa[N],f[N][2][2][2],cnt1[N];
ll head[N],l,b[N];
re e[N*2];
void arr(ll x,ll y)
{
  e[++l].a=head[x];
  e[l].b=y;
  head[x]=l;
}
bool tt=0;
void cl(int x)
{
    if (cnt1[x]==0) cnt1[x]++;
    else tt=1;
}
void mina(int &x,int y)
{
    if (y<x) x=y;
}
void solve(ll x,ll v,int k)
{
  for (ll i=v;i!=x;i=fa[i])
  {
      cl(b[i]); cl(b[i]^1);
  }
  cl(k); cl(k^1);
  ll g[2][2][2][2][3];
  me1(g);
  rep(i1,0,1)
    rep(j1,0,1)
      rep(k1,0,1)
        rep(t,0,2)
        {
          bool t1=i1|(t==0);
          bool t2=j1|(t==1);
          int t3=k1+(t==2);
          if (t1&t2||t3>=2) continue;
          g[t1][t2][t3][t%2][t]=min(g[t1][t2][t3][t%2][t],f[v][i1][j1][k1]+t);
        }
  for (ll i=fa[v];i!=fa[x];i=fa[i])
  {
      ll h[2][2][2][2][3]; me1(h); 
      rep(i1,0,1)
      rep(j1,0,1)
        rep(k1,0,1)
          rep(i2,0,1)
            rep(j2,0,1)
              rep(k2,0,1)
                rep(t,0,2)
                { 
                  bool t1=i2|(t==0);
                  bool t2=j2|(t==1);
                  int t3=k2+(t==2);
                  if ((t1&t2)||t3>=2) continue;
                  t1=i1|(t==0);
                  t2=j1|(t==1);
                  t3=k1+(t==2);
                  if ((t1&t2)||t3>=2) continue;
                  rep(p1,0,1)
                     rep(p2,0,2)
                       mina(h[t1][t2][t3][(p1+t)%2][p2],f[i][i1][j1][k1]+g[i2][j2][k2][p1][p2]+t);
                 }
     mep(g,h); 
  }
  me1(f[x]);
  rep(i1,0,1)
    rep(j1,0,1)
      rep(k1,0,1)
        rep(p1,1,1)
          rep(t,0,2)
          {
               bool t1=i1|(t==0);
             bool t2=j1|(t==1);
             int t3=k1+(t==2);
             if (t1&t2||t3>=2) continue;
             mina(f[x][t1][t2][t3],g[i1][j1][k1][p1][t]);
          }
}
void tarjan(ll x,ll y)
{
  if (tt) return;
  dfn[x]=low[x]=++cnt;
  for (ll u=head[x];u;u=e[u].a)
  {
    ll v=e[u].b;
    if (v==y) continue;
    if (!dfn[v])
    {
        fa[v]=x; b[v]=u;
        tarjan(v,x);
        low[x]=min(low[x],low[v]);
    } else low[x]=min(low[x],dfn[v]);
    if (low[v]>dfn[x]) 
    {
        ll g[2][2][2];
        me1(g);
        rep(i1,0,1)
          rep(j1,0,1)
            rep(k1,0,1)
              rep(i2,0,1)
                rep(j2,0,1)
                  rep(k2,0,1)
                    rep(t,0,2)
                    {
                        bool t1=i2|(t==0);
                        bool t2=j2|(t==1);
                        int t3=k2+(t==2);
                        if ((t1&t2)||t3>=2) continue;
                        t1=i1|(t==0);
                        t2=j1|(t==1);
                        t3=k1+(t==2);
                        if ((t1&t2)||t3>=2) continue;
                        g[t1][t2][t3]=min(g[t1][t2][t3],f[x][i1][j1][k1]+f[v][i2][j2][k2]+t);
                    }
        mep(f[x],g);
    } 
  }
  for (ll u=head[x];u;u=e[u].a)   {
        ll v=e[u].b;
        if (fa[v]!=x&&dfn[v]>dfn[x]) solve(x,v,u);
    }
}
int main()
{
   ios::sync_with_stdio(false);
   l=1;
   cin>>n>>m;
   rep(i,1,m)
   {
        ll u,v;
        cin>>u>>v;
        arr(u,v); arr(v,u);
   }
   ll ans=0;
   rep(i,1,n)
   if (!dfn[i])
   {  
      tarjan(i,0);
      vector<int> ve;
      rep(i1,0,1)
        rep(j1,0,1)
          rep(k1,0,1)
            ve.push_back(f[i][i1][j1][k1]);
      sort(ve.begin(),ve.end());
      ans+=ve[0]; 
   }
   if (tt||ans>2*m) cout<<-1<<endl;
   else
   {
       cout<<ans<<endl;
   }
   return 0;
}
View Code

3.仙人掌上最短路

这个题一定要建出圆方树

圆方树的建立方法是对于树边直接连，对于环边把环边都连到一个新点上

定义老点叫做圆点新点叫做方点

圆点到圆点的距离就是原树距离

圆点到方点的距离就是圆点到环上dfs序最小点的环上最短距离

求两个点距离时，先求出lca=k

若k是圆点，距离就是lca[x]+lca[y]-2*lca[k]

若k是方点，距离就是lca[x]+lca[y]-lca[a]-lca[b]+dis(a,b)

其中a,b分别代表x,y到k差一步的点，dis(a,b)代表a，b在环上的距离

正确性比较容易证明

圆方树
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

//#include <immllrin.h>
//#include <emmllrin.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,h,t) for (ll i=h;i<=t;i++)
#define dep(i,t,h) for (ll i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define IL inline
#define rll register ll
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
char ss[1<<24],*A=ss,*B=ss;
IL char gc()
{
    return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void maxa(T &x,T y)
{
    if (y>x) x=y;
}
template<class T>void mina(T &x,T y)
{
    if (y<x) x=y;
}
template<class T>void read(T &x)
{
    ll f=1,c; while (c=gc(),c<48||c>57) if (c==‘-‘) f=-1; x=(c^48);
    while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f;
}
struct cp {
    ll x,y;
    cp operator +(cp B)
    {
        return (cp){x+B.x,y+B.y};
    }
    cp operator -(cp B)
    {
        return (cp){x-B.x,y-B.y};
    }
    ll operator *(cp B)
    {
        return x*B.y-y*B.x;
    }
    ll half() { return y < 0 || (y == 0 && x < 0); }
};
struct re{
    ll a,b,c;
};
const ll N=3e5;
ll n,m,q,f1,f2;
ll dis[N],s[N],b[N];
ll id[N];
struct yy{
    re e[N*2];
    ll head[N],d[N]; 
    ll bz[20][N],l;
    void arr(ll x,ll y,ll z)
    { 
        e[++l].a=head[x];
        e[l].b=y;
        e[l].c=z;
  //      if (x<y) cerr<<x<<" "<<y<<endl;
        head[x]=l;
    }
    void dfs(ll x,ll y)
    {
       bz[0][x]=y;
       rep(i,1,19) bz[i][x]=bz[i-1][bz[i-1][x]];
       for (ll u=head[x];u;u=e[u].a)
       {
            ll v=e[u].b;
            if (v==y) continue;
            dis[v]=dis[x]+e[u].c;
            d[v]=d[x]+1;
            dfs(v,x);
       }
    }
    ll lca(ll x,ll y)
    {
        if (d[x]<d[y]) swap(x,y);
        dep(i,19,0) if (d[bz[i][x]]>=d[y]) x=bz[i][x];
        if (x==y) return x;
        dep(i,19,0) if (bz[i][x]!=bz[i][y]) x=bz[i][x],y=bz[i][y];
        f1=x; f2=y;
        return bz[0][x];
    }
}G2;
struct xx{
  ll dfn[N],low[N],cnt,fa[N],n;
  ll head[N],l;
  re e[N*2];
  void arr(ll x,ll y,ll z)
  {
      e[++l].a=head[x];
      e[l].b=y;
      e[l].c=z;
      head[x]=l;
  }
  void solve(ll x,ll v,ll w)
  { 
     n++;
     ll now=w,now2=0;
     for (ll i=v;i!=fa[x];i=fa[i])
     {
         s[i]=now;
         now+=b[i];
         id[i]=now2++;
     }
     s[n]=s[x]; s[x]=0;
     for (ll i=v;i!=fa[x];i=fa[i]) G2.arr(n,i,min(s[i],s[n]-s[i])),G2.arr(i,n,min(s[i],s[n]-s[i]));
  }
  void tarjan(ll x,ll y)
  {
    dfn[x]=low[x]=++cnt; 
    for (ll u=head[x];u;u=e[u].a)
    {
        ll v=e[u].b;
        if (v==y) continue;
        if (!dfn[v])
        {
            fa[v]=x; b[v]=e[u].c;
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
        } else low[x]=min(low[x],dfn[v]);
        if (low[v]>dfn[x]) {G2.arr(x,v,e[u].c); G2.arr(v,x,e[u].c);} 
    }
    for (ll u=head[x];u;u=e[u].a)
    {
        ll v=e[u].b;
        if (fa[v]!=x&&dfn[v]>dfn[x]) solve(x,v,e[u].c);
    }
  }
}G1;
int main()
{
   ios::sync_with_stdio(false);
   cin>>n>>m>>q;
   rep(i,1,m)
   {
        ll u,v,w;
        cin>>u>>v>>w;
        G1.arr(u,v,w); G1.arr(v,u,w);
   } 
   G1.n=n;
   G1.tarjan(1,0);
   G2.dfs(1,0);
   rep(i,1,q)
   {
         ll u,v;
         cin>>u>>v;
         ll g=G2.lca(u,v);
         if (g<=n) cout<<dis[u]+dis[v]-2*dis[g]<<endl;
         else
         {
             ll ans=dis[u]+dis[v]-dis[f1]-dis[f2];
             if (id[f1]<=id[f2]) ans+=min(s[f1]+s[g]-s[f2],s[f2]-s[f1]);
             else ans+=min(s[f2]+s[g]-s[f1],s[f1]-s[f2]);;
             cout<<ans<<endl;
         }
   }
   return 0;
}
View Code

 

圆方树

上一篇：CopyOnWriteArrayList类


下一篇：循环三兄弟for while until，（如果可以循环，让我再次感受曾挥霍的昨天。）