CF51F Caterpillar (边双+树形DP)

题目传送门

题目大意：给你一张n个点m条边的图。每次操作可以把两个点合并成一个(与之相连的边也都要连到新点上)。求把图中每个联通块都变成“毛毛虫”的最小操作次数。“毛毛虫”必须是一棵树(可以存在自环)，且其中必须存在一条主链，使得主链外的点到主链上的任意一点距离为1。$n\leq 2000,m\leq 10^{5}$

树上乱搞题目×1

首先把原图用边双$tarjan$缩成一棵树

然后我们想办法找出这条主链，似乎也只能$DP$了

定义$f(x,0/1)$表示主链一端在$x$子树内另一端在$x$点/主链两个端点都在$x$子树内付出的最小代价

对于不在主链上的点，需要把整颗子树合并成一个点，画一画图发现这个数量就是这个子树内的叶节点数量！

$f(x,0)=min{f(v,0)+合并其他子树的花费}$

$f(x,1)=min(f(v_{0},0)+f(v_{1},0)+合并其他子树的花费)$

合并其他子树的花费很好推，但式子太长就不放了

这也意味着我们$DP$时需要挑一个非叶节点为根进行$DP$

题目并没有保证所有点都在一个联通块内..每个联通块都要统计一遍，好麻烦..

时间可以被菊花图卡成$O(n^{2})$，但仍能轻松通过全部数据

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 2010

 #define M1 100050

 using namespace std;

 const int inf=0x3f3f3f3f;

 template <typename _T> void read(_T &ret)

 {

     ret=; _T fh=; char c=getchar();

     while(c<''||c>''){ if(c=='-') fh=-; c=getchar(); }

     while(c>=''&&c<=''){ ret=ret*+c-''; c=getchar(); }

     ret=ret*fh;

 }

 struct Edge{

 int to[M1*],nxt[M1*],val[M1*],head[N1],cte;

 void ae(int u,int v,int w)

 { cte++; to[cte]=v; nxt[cte]=head[u]; val[cte]=w; head[u]=cte; }

 }e,g;

 int n,m,num;

 int dfn[N1],low[N1],use[N1],stk[N1],dad[N1],tp,tim,que[N1],tl;

 int f[N1][],sum[N1],sz[N1],inc[N1],vis[N1];

 void init()

 {

     memset(f,,(num+)*);   memset(sz,,(num+)*);  memset(sum,,(num+)*);

     memset(vis,,(num+)*); memset(inc,,(num+)*); memset(g.head,,(num+)*);

     tl=tp=tim=num=; g.cte=;

 }

 void tarjan(int x,int fa)

 {

     int j,v; que[++tl]=x;

     dfn[x]=low[x]=++tim; use[x]=; stk[++tp]=x;

     for(j=e.head[x];j;j=e.nxt[j])

     {

         if(e.val[j]==fa) continue;

         v=e.to[j];

         if(!dfn[v]){

             tarjan(v,e.val[j]);

             low[x]=min(low[x],low[v]);

         }else if(use[v]){

             low[x]=min(low[x],dfn[v]);

         }

     }

     if(low[x]==dfn[x])

     {

         num++;

         while(stk[tp]!=x)

             use[stk[tp]]=, dad[stk[tp]]=num, tp--;

         use[stk[tp]]=, dad[stk[tp]]=num, tp--;

     }

 }

 void dfs(int x,int fa)

 {

     int j,v; sz[x]=; vis[x]=;

     for(j=g.head[x];j;j=g.nxt[j])

     {

         v=g.to[j]; if(v==fa) continue;

         dfs(v,x);

         sz[x]+=sz[v]; sum[x]+=sum[v];

     }

     int k,v0,v1;

     if(inc[x]>) f[x][]=f[x][]=inf; else sum[x]=;

     for(j=g.head[x];j;j=g.nxt[j])

     {

         v0=g.to[j]; if(v0==fa) continue;

         f[x][]=min(f[x][],f[v0][]+(sz[x]--sz[v0])-(sum[x]-sum[v0]));

         for(k=g.nxt[j];k;k=g.nxt[k])

         {

             v1=g.to[k]; if(v1==fa) continue;

             f[x][]=min(f[x][],f[v0][]+f[v1][]+(sz[x]-sz[v0]-sz[v1]-)-(sum[x]-sum[v0]-sum[v1]));

         }

     }

 }

 int de;

 int solve(int x)

 {

     int i,j,ans=,root; init();

     tarjan(x,);

     if(num<=){ return tl-num; }

     for(i=;i<=tl;i++)

     {

         x=que[i];

         for(j=e.head[x];j;j=e.nxt[j]) if(dad[x]!=dad[e.to[j]])

             g.ae(dad[x],dad[e.to[j]],), inc[dad[e.to[j]]]++;

     }

     for(i=;i<=num;i++) if(inc[i]>){ root=i; dfs(root,); break; }

     for(i=,ans=inf;i<=num;i++) if(inc[i]>)

         if(i!=root) ans=min(ans,f[i][]+(num-sz[i])-(sum[root]-sum[i]));

         else ans=min(ans,f[i][]);

     return ans+tl-num;

 }

 int main()

 {

     int i,j,x,y,ans=-;

     scanf("%d%d",&n,&m);

     for(i=;i<=m;i++) read(x), read(y), e.ae(x,y,i), e.ae(y,x,i);

     for(i=;i<=n;i++) if(!dfn[i]) ans+=solve(i)+;

     printf("%d\n",ans);

     return ;

 }

巴特西

CF51F Caterpillar (边双+树形DP)

最新文章

热门文章