题解 CF238C【World Eater Brothers】

Loser_King · 2022-02-11 16:08:05 · 题解

模拟赛 T3，赛时写了部分分（10pts+20pts）来不及写正解了（悲）

题意

给定一棵边有方向的树，求出至少将几条边反转方向后满足没有入度的结点最多有两个。

n\le 3000

做法

虽然 n\le 3000，O(n^2) 是可以过的，但是实际上本题存在 O(n) 的简单做法，

本篇题解对 O(n^2) 做法不再描述。

考虑树形 DP。（为方便，下称以 x 为根的子树为 x 子树）

状态：f_{i,j,k} 表示 i 子树中，当前有 j 个结点没有入度（包括 i 结点本身），且当前 i 是否有入度（k=0/1）。容易发现这样的状态没有后效性。
转移：考虑 x 结点要合并其儿子 y 的答案时边 x-y 的方向，即图中的 ↕(*)。

(x) o---┐
    ↕   |
(y)┌o┐ ┌┴┐
   |j| |i|
   └-┘ └-┘

枚举当前 x 子树已合并部分中没有入度的点数 i 和 y 子树中没有入度的点数 j，以及 x 和 y 结点分别是否有入度，记为 k_x 和 k_y (0\le i+j\le 2,0\le k_x,k_y \le 1)。

若确定这条边的方向为 x\Rightarrow y，那么 y 结点已有入度。若其在 y 子树状态中没有入度，则需将其从没有入度的点中删去。

可以得到 f_{x,i+j,k_x}=\min(w+f_{x,i,k_x}+f_{y,j+k_y,k_y}) 。其中 w 为将这条边方向设为 x\Rightarrow y 的费用。
同理，若确定这条边的方向为 x\Leftarrow y，那么 x 结点已有入度。若其在 x 子树之前的状态中没有入度，则需将其从没有入度的点中删去。

可以得到 f_{x,i+j,0}=\min(w+f_{x,i+k_x,k_x}+f_{y,j,k_y}) 。其中 w 为将这条边方向设为 x\Leftarrow y 的费用。

实际转移的时候需要使用辅助数组 g 记录，防止状态发生重叠。

初始：f_{x,1,1}=0，表示只有根节点的树没有入度，且不需花费。其他状态皆为无穷大。
答案：\min\limits_{0\le j\le 2,0\le k\le 1} f_{root,j,k}，其中 root 为指定的树根，树形 DP 的起点。

读入时建边 x\xrightleftharpoons[1]{0} y，表示将边方向变为 x\Rightarrow y 的代价为 0，将边方向变为 x\Leftarrow y 的代价为 1。

由 DP 过程可知时间复杂度为 O(n) 。

事实上这种 DP 可以解决类似于”没有入度的结点最多有 k 个“的问题，时间复杂度为 O(nk^2) 。

代码

目前是洛谷和 CF（并列）最快解。

//CF238C AC Code
//written by Loser_King(159686)
//180ms(30ms) / 950B
#include<bits/stdc++.h>
#define to first
#define val second
using namespace std;
int const N=3010,INF=0x3f3f3f3f;
int n,f[N][8][2],g[8][2];
vector<pair<int,int> >e[N];
void add_edge(int x,int y,int v){
    e[x].push_back({y,v});
}
void tomin(int&x,int y){
    if(x>y)x=y;
}
void dfs(int x,int fa){
    f[x][1][1]=0;
    for(auto t:e[x]){
        int y=t.to,w=t.val;
        if(y==fa)continue;
        dfs(y,x);
        memset(g,INF,sizeof g);
        for(int i=0;i<3;i++)
            for(int j=0;j<3-i;j++)
                for(int kx=0;kx<2;kx++)
                    for(int ky=0;ky<2;ky++)
                        tomin(g[i+j][kx],f[x][i][kx]+f[y][j+ky][ky]+w),//x->y
                        tomin(g[i+j][0],f[x][i+kx][kx]+f[y][j][ky]+(w^1));//y->x
        memcpy(f[x],g,sizeof g);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        add_edge(x,y,0),add_edge(y,x,1);
    }
    memset(f,INF,sizeof f);
    dfs(1,0);
    int ans=INF;
    for(int i=0;i<6;i++)
        tomin(ans,f[1][i/2][i&1]);
    cout<<ans<<"\n";
}