LOJ 2547 「JSOI2018」防御网络——思路+环DP

时间:2021-07-13 00:23:25

题目:https://loj.ac/problem/2547

一条树边 cr->v 会被计算 ( n-siz[v] ) * siz[v] 次。一条环边会被计算几次呢?于是去写了斯坦纳树。

LOJ 2547 「JSOI2018」防御网络——思路+环DPLOJ 2547 「JSOI2018」防御网络——思路+环DP
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
int rdn()
{
  int ret=0;bool fx=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}
  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
  return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int mod=1e9+7;
int upt(int x){while(x>=mod)x-=mod;while(x<0)x+=mod;return x;}
int pw(int x,int k)
{int ret=1;while(k){if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}

int n,m;
namespace S1{
  const int N=10,M=(1<<8)+5;
  int hd[N],xnt,to[N<<2],nxt[N<<2];
  int bin[N],dp[N][M],dis[N][N]; bool vis[N];
  queue<int> q;
  void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
  void init()
  {
    for(int i=1;i<=n;i++)
      {
    memset(vis,0,sizeof vis);
    q.push(i); vis[i]=1;
    while(q.size())
      {
        int k=q.front(); q.pop();
        for(int i=hd[k],v;i;i=nxt[i])
          if(!vis[v=to[i]])
        { vis[v]=1;dis[i][v]=dis[i][k]+1;q.push(v);}
      }
      }
    bin[0]=1;for(int i=1;i<=n;i++)bin[i]=bin[i-1]<<1;
  }
  void solve()
  {
    for(int i=1,u,v;i<=m;i++)
      u=rdn(),v=rdn(),add(u,v),add(v,u);
    init();
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++)dp[i][bin[i-1]]=0;
    int ans=0;
    for(int s=1;s<bin[n];s++)
      {
    for(int i=1;i<=n;i++)
      for(int t=(s-1)&s;t;t=(t-1)&s)
        dp[i][s]=Mn(dp[i][s],dp[i][t]+dp[i][s^t]);
    for(int i=1;i<=n;i++)q.push(i),vis[i]=1;
    while(q.size())
      {
        int k=q.front(); q.pop(); vis[k]=0;
        for(int i=hd[k],v;i;i=nxt[i])
          if(dp[v=to[i]][s]>dp[k][s]+1)
        {
          dp[v][s]=dp[k][s]+1;
          if(!vis[v])q.push(v),vis[v]=1;
        }
      }
    int mn=dp[1][s];
    for(int i=2;i<=n;i++)mn=Mn(mn,dp[i][s]);
    ans=upt(ans+mn);
      }
    ans=(ll)ans*pw(bin[n],mod-2)%mod;
    printf("%d\n",ans);
  }
}
int main()
{
  n=rdn();m=rdn();
  if(n<=8){S1::solve();return 0;}
  return 0;
}
View Code

不应从每条环边的角度考虑,而要从每个环的角度考虑。思维还是不足。

想算一个环上有 len 条边被选的方案。

记一个“环外子树(含自己这点)中有点被选的环上点” 为 “被选的点” 。

首先考虑如果有一个选点方案,这个环会被怎么选边。为了把点都连通,被选的点两两之间应该连通。

所以环上没被选的边一定是最远的两个相邻的被选的点之间的部分。

想求一个环 “最远相邻被选点的间隔为 len ” 的方案。注意到 “最远相邻被选点的间隔 <=len ”的方案容易 DP 。

断环成链,dp[ i ][ j ] 表示 i 点和 j 点要选,[ i , j ] 之间被选点间隔 <=len 的方案。则 \( dp[i][j]=f[j]*\sum\limits_{k=j-len}^{j-1}dp[i][k] \) ,其中 \( f[j] \) 是选 j 点的方案,即 ( 2环外子树大小 -1 ) 。

前缀和优化即可。对于一个 len ,合法的 dp[ i ][ j ] 应该满足 (cnt - j) + i <=len (cnt 是环点个数)。把这些加到 g[ len ] 上,用 (cnt-len) * (g[ len ] - g[ len-1 ]) 贡献答案即可。

求环外子树大小要小心。注意清空数组。注意分辨不同的环。可以给环最浅的点打标记,特殊求该点的环外子树大小。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=205,M=N<<2,mod=1e9+7;
int upt(int x){while(x>=mod)x-=mod;while(x<0)x+=mod;return x;}
int pw(int x,int k)
{int ret=1;while(k){if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}

int n,m,hd[N],xnt,to[M],nxt[M],spe[N];
int dp[N],pr[N],f[N],g[N],siz[N],ans,bin[N];
int tim,dfn[N],low[N],sta[N],top,cnt,col[N],qnt,q[N];
bool vis[N],ins[N];
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void tarjan(int cr,int fa)
{
  dfn[cr]=low[cr]=++tim; sta[++top]=cr; ins[cr]=1;
  siz[cr]=1;
  for(int i=hd[cr],v;i;i=nxt[i])
    if((v=to[i])!=fa)
      {
    if(!dfn[v])
      {tarjan(v,cr);low[cr]=Mn(low[cr],low[v]);siz[cr]+=siz[v];}
    else if(ins[v])low[cr]=Mn(low[cr],dfn[v]);
      }
  if(dfn[cr]==low[cr])
    {
      if(sta[top]==cr){ins[cr]=0;top--;return;}
      cnt++;
      do{int v=sta[top];ins[v]=0;col[v]=cnt;}while(sta[top--]!=cr);
      spe[cr]=fa;//fa can be 0 but no influence
    }
}
void dfsx(int cr)
{
  q[++qnt]=cr; vis[cr]=1; int id=qnt;
  for(int i=hd[cr],v;i;i=nxt[i])
    if(!vis[v=to[i]]&&col[v]==col[cr])dfsx(v);//col==
    else if(col[v]!=col[cr]&&v!=spe[cr])//include !col
      f[id]+=siz[v];//col!= not !col//v!=spe[cr]
  if(spe[cr])
    f[id]+=n-siz[cr];//+= not =//n-siz[cr] not spe-siz[cr]
  f[id]++;
}
void solve(int cr)
{
  for(int i=1;i<=qnt;i++)f[i]=0; qnt=0;//f[i]=0//qnt=0
  dfsx(cr);
  for(int len=1;len<=qnt;len++)
    {
      g[len]=0;
      for(int i=1;i<=len;i++)
    {
      dp[i]=bin[f[i]]; pr[i]=dp[i]; pr[i-1]=0;
      int lm=qnt-len+i;
      if(i>=lm)g[len]=upt(g[len]+dp[i]);
      for(int j=i+1;j<=qnt;j++)
        {
          dp[j]=(ll)upt(pr[j-1]-pr[Mx(i,j-len)-1])*bin[f[j]]%mod;
          pr[j]=upt(pr[j-1]+dp[j]);
          if(j>=lm)g[len]=upt(g[len]+dp[j]);
        }
    }
    }
  for(int len=1;len<qnt;len++)
    ans=(ans+(ll)(qnt-len)*upt(g[len]-g[len-1]))%mod;
}
void dfs(int cr)
{
  if(col[cr]&&!vis[cr])solve(cr); ins[cr]=1;//not use vis again
  for(int i=hd[cr],v;i;i=nxt[i])
    if(!ins[v=to[i]])
      {
    if(col[cr]!=col[v]||!col[cr])
      //col!= not !col||!col//also !col
      ans=(ans+(ll)bin[siz[v]]*bin[n-siz[v]])%mod;
    dfs(v);
      }
}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1,u,v;i<=m;i++)
    scanf("%d%d",&u,&v),add(u,v),add(v,u);
  bin[0]=1;for(int i=1;i<=n;i++)bin[i]=upt(bin[i-1]<<1);
  for(int i=1;i<=n;i++)bin[i]=upt(bin[i]-1);//
  tarjan(1,0); dfs(1);
  ans=(ll)ans*pw(bin[n]+1,mod-2)%mod;
  printf("%d\n",ans);
  return 0;
}