题解 P4517 【[JSOI2018]防御网络】

· · 题解

我们考虑贡献……

本题题解

首先众所周知的是一般图的斯坦纳树是只能大力状压dp的……

但是这是一颗点仙人掌，情况会变的有趣很多……

还是一个非常传统的套路叫做考虑贡献

直接O(2^n)的枚举点集求出合法的边集可能不是非常好做……

但是如果我们考虑某一个边(u,v)在多少个点集的斯坦纳树当中出现了情况会怎样呢？

case1:(u,v)是割边

此时我们割掉这个边会产生两个联通块

我们发现如果点集全部落在同一个联通块的时候，这个边一定不会在斯坦纳树当中出现(因为没有点需要借助这个边来联通)，但是如果这个点集有一部分在左边另一部分在右边，由于我们至少需要保证左右是联通的，因此这条边一定出现在斯坦树当中

所以斯坦纳树包含边(u,v)的点集一共有(2^{siz}-1)(2^{n-siz}-1)种(siz为其中一个联通块的点数)(左边合法方案×右边合法方案)

那么我们可以先使用tarjan算法找出所有的割边然后把它们的贡献先算了

case2:(u,v)是环边

此时直接考虑(u,v)的贡献不是非常方便了，我们考虑直接把整个环的贡献算出来

我们割掉这个环上的边(注意不是点！)会产生好几个联通块

那么我们发现如果点集落在同一个联通块当中的话环上的边都不会出现在斯坦纳树当中

如果有若干个子联通块中的点被选中了的话，这些点想要联通至少需要先到环上，换句话说每个子联通块可以缩到环上的一个点上。(如果子联通块中的点被选中我们就认为环上的点被选中)

那么缩完点之后我们会发现把这些点联通的唯一方式就是用一条链把这些点串起来，换个角度看就是假如环上有k个点被选中，相邻两个点之间会产生k条路径，我们把这k条路径中的最大值切掉，剩下的长链就是最小的代价了，也就是说，这条长链将会出现在斯坦纳树当中

所以我们考虑计算每一条长度为k的长链的贡献，换句话说我们要计算有多少点集的斯坦纳树存在一条在环上的长度为k的长链

那么我们尝试使用动态规划解决这个问题

(以下的点集指的是缩点之后的点集)

先破环为链，然后设Dp_{i,j}为选中的点中最右点为i，两两路径的最大值为k的点集方案数(不考虑最左点和最右点之间的路径)

此时我们遇到了一个很麻烦的问题，我们没法从一个状态当中知道相邻两个点路径，因为我们的状态里并没有记录最左点和最右点之间的路径长度，而记了我们就没有办法转移(因为你把最右点拓展出去之后最左点和最右点的路径长度在缩短……，然后你就不知到你记的最大值是不是真的最大值了)

数据范围只有200,所以给状态再加上一维，Dp_{i,j,k}表示最左点为i，最右点为j，不考虑i，j之间的路径情况下两两间路径最大值为k的点集数量

那么Dp_{i,j,k}对答案的贡献就是(环长-max(k,环长+i-j))×Dp_{i,j,k}了

那么怎么转移呢？

当然是暴力枚举上一个最右点的位置了……

所以转移方程大概长这样……siz_{j}表示割掉j的左右环边之后剩下的联通块点的个数

Dp_{i,j,k}=(2^{siz_{j}}-1)(\sum_{p=0}^{k}Dp_{i,j-k,p}+\sum_{p=j-k+1}^{j-1}Dp_{i,p,k})

第一部分是j和上一个点的路径长度恰好等于k的情况(此时上一个点的最大值可以任取)，第二部分是j和上一个点的路径长度小于k的情况(此时上一个点的最大值只能为k)

你发现转移方程里面的两个\Sigma是可以使用前缀和表示的形式(一个是行的前缀和，另一个是列的前缀和)

那么我们真实dp的时候只需要记录前缀和数组就行了，dp值现场计算，现场算贡献，现场更新前缀和就可以了

实现

实现的时候可能会有一点小trick

首先先使用tarjan求出所有的割边，然后把这个割边标记一下

发现一件事情是割边一定是你这张图的dfs树的树边，因此我们可以处理出来割掉割边(u,v)之后u所在联通块的siz和v所在联通块的siz 分别存储在(u->v)当中和(v->u)当中

然后我们要统计割掉环之后的siz的话我们可以枚举环上的点的每一个出边的割边，然后就可以统计siz了

关于寻找环的话由于我们需要按照相邻两个点有连边的顺序把环中的点拉出来，所以删去所有割边之后dfs即可提取出环 另外就是我们寻找环的时候可能需要把环中的点拉出来塞到一个队列里大力dp，注意重新编号的问题。

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=210;const int E=1e3+10;typedef long long ll;const ll mod=1e9+7;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}int siz[N];
int n;int m;int v[E];int x[E];int ct=1;int al[N];int low[N];int dfn[N];int df;bool book[E];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}ll res;bool mrk[N];int w[E];
inline int tarjan(int u,int f)//tarjan找割边
{
    dfn[u]=low[u]=++df;siz[u]=1;
    for(int i=al[u];i;i=x[i])
    {
        if(v[i]==f)continue;
        if(dfn[v[i]]==0){low[u]=min(low[u],tarjan(v[i],u));siz[u]+=siz[v[i]];}
        else {low[u]=min(low[u],dfn[v[i]]);}
        if(low[v[i]]>dfn[u])
        {
            book[i]=book[i^1]=true;res+=(po(2,siz[v[i]])-1)*(po(2,n-siz[v[i]])-1);
            w[i]=siz[v[i]];w[i^1]=n-siz[v[i]];
        }
    }return low[u];
}
inline int nxt(int p)//找环上的后继
{for(int i=al[p];i;i=x[i])if(book[i]==false&&mrk[v[i]]==false)return v[i];return 0;}
ll sum1[N][N];ll sum2[N][N];int q[N];int hd;ll val[N];
inline void solve(int st)//dp
{
    for(int p=st;p;p=nxt(p))q[++hd]=p,mrk[p]=true;if(hd==1){hd=0;return;}
    for(int i=1;i<=hd;i++)val[i]=1;
    for(int i=1;i<=hd;i++)for(int j=al[q[i]];j;j=x[j])val[i]+=w[j];
    for(int i=1;i<=hd;i++)val[i]=po(2,val[i])-1;
    for(int i=1;i<hd;i++)
    {
        for(int j=0;j<=hd;j++)sum2[i][j]=val[i];
        for(int j=i+1;j<=hd;j++)//注意前缀和
            for(int k=1;k<=hd;k++)
            {
                ll dp=0;if(j-k>=i)
                {
                    dp=(sum2[j-k][k]+sum1[j-1][k]+mod-sum1[j-k][k])*val[j]%mod;
                    int mx=max(hd-j+i,k);(res+=dp*(hd-mx))%=mod;
                }sum1[j][k]=(sum1[j-1][k]+dp)%mod;sum2[j][k]=(sum2[j][k-1]+dp)%mod;
            }
        for(int j=i;j<=hd;j++)for(int k=0;k<=hd;k++)sum1[j][k]=0;
        for(int j=i;j<=hd;j++)for(int k=0;k<=hd;k++)sum2[j][k]=0;
    }hd=0;
}
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);}tarjan(1,0);
    for(int i=1;i<=n;i++){if(!mrk[i])solve(i);}printf("%lld",res*po(po(2,n),mod-2)%mod);
    return 0;//拜拜程序
}