【题解】Luogu P2899 [USACO008JAN] 手机网络树形dp

川长思鸟来 2023-08-17 16:49 104阅读 0赞

每个点的状态只和他的父亲和儿子有关

转移方程：

$f\[i\]\[0\]$ i放

$f\[i\]\[1\]$ i不放，儿子放

$f\[i\]\[2\]$ i不放，父亲放

j是i的一个儿子

i放，可以覆盖自己、父亲和儿子。i放的情况下，j可以放或不放

$f\[i\]\[0\]+=min(f\[j\]\[0\],f\[j\]\[1\],f\[j\]\[2\])$

i的父亲放，可以覆盖i的父亲和i。j只能选择自己放或被儿子覆盖

$f\[i\]\[2\]++min(f\[j\]\[0\],f\[j\]\[1\])$

从i的儿子中，选一个去覆盖i，其余的按照f\[i\]\[2\]转移

$f\[i\]\[1\]=f\[j\]\[0\]+\{\\sum\}min(f\[son\]\[0\],f\[son\[1\])$

优化：

对于j，有$f\[i\]\[1\]=f\[j\]\[0\]+\{\\sum\}min(f\[son\]\[0\],f\[son\[1\])$

如果j不是最优的，有k满足

$f\[j\]\[0\]+\{\\sum\}min(f\[son\]\[0\],f\[son\[1\])<f\[k\]\[0\]+\{\\sum\}min(f\[son\]\[0\],f\[son\[1\])$

$f\[j\]\[0\]-min(f\[son\]\[0\],f\[son\]\[1\])>f\[k\]\[0\]-min(f\[son\]\[1\],f\[son\]\[0\])$

所以对于最优的j，一定有$f\[x\]\[0\]-min(f\[son\]\[0\],f\[son\]\[1\])$是所有儿子里最小的

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5 const int maxn=1e4+10;
     6 const int inf=1e9+7;
     7 inline int read(){
     8     int x=0,f=1;
     9     char c=getchar();
    10     while(c<'0'||c>'9'){
         if(c=='-')f=-1;c=getchar();}
    11     while(c>='0'&&c<='9'){x=(x*10)+c-'0';c=getchar();}
    12     return x*f;
    13 }
    14 struct edge{
    15     int nxt,to;
    16 }e[maxn*2];
    17 int head[maxn],cnt;
    18 int f[maxn][3],n;
    19 inline void add(int from,int to){
    20     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
    21 }
    22 void dfs(int x,int fa){
    23     int son=0;f[x][0]=1;
    24     for(int i=head[x];i;i=e[i].nxt){
    25         int y=e[i].to;
    26         if(y==fa)continue;
    27         dfs(y,x);
    28         f[x][0]+=min(f[y][0],min(f[y][1],f[y][2]));
    29         f[x][2]+=min(f[y][0],f[y][1]);
    30         if((f[son][0]-min(f[son][1],f[son][0]))>(f[y][0]-min(f[y][1],f[y][0]))){
    31             son=y;
    32         }
    33     }
    34     f[x][1]=f[son][0];
    35     for(int i=head[x];i;i=e[i].nxt){
    36         int y=e[i].to;
    37         if(y==fa||son==y)continue;
    38         f[x][1]+=min(f[y][0],f[y][1]);
    39     }
    40 }
    41 int main(){
    42     n=read();
    43     for(int i=1;i<n;i++){
    44         int a,b;
    45         a=read();b=read();
    46         add(a,b);add(b,a);
    47     }
    48     f[0][0]=inf;
    49     dfs(1,-1);
    50     printf("%d",min(f[1][0],f[1][1]));
    51     return 0;
    52 }
    53 }
    54 signed main(){
    55   gengyf::main();
    56   return 0;
    57 }

--------------------

好几倍经验题

P2458 P3267 P3942 P2016 P2279...

转载于:https://www.cnblogs.com/gengyf/p/11592793.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/27264af8b7194ef2aaf45e2097c7bc9d.png