[USACO08JAN] 手机网络

经典问题系列

覆盖半径\(1\)的最小点覆盖集

\(f[i][0]\) 表示不在此处建信号塔，但\(i\)及其子树都有信号

\(f[i][1]\) 表示在此处建信号塔，但\(i\)及其子树都有信号

\(f[i][2]\) 表示不在在此处建信号塔，但\(i\)子树都有信号，而\(i\)无信号

\(f[p][2]=\sum f[q][0]\)

\(f[p][1]=\sum min(f[q][0],f[q][1],f[q][2])\)

\(f[p][0]=min_q (f[q][1]+\sum_k min(f[k][0],f[k][1]))\)

答案就是 \(min(f[1][0],f[1][1])\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1000005;

vector <int> g[N];

int vis[N],f[N][3],t1,t2,t3,n;

void dfs(int p) {

    vis[p]=1;

    int fa=0;

    f[p][1]=1;

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i];

        if(vis[q]==0) {

            dfs(q);

            f[p][2]+=f[q][0];

            f[p][1]+=min(f[q][0],min(f[q][1],f[q][2]));

        }

        else fa=q;

    }

    f[p][0]=1e+16;

    for(int i=0;i<g[p].size();i++) {

        int q=g[p][i];

        if(q!=fa) {

            int tmp=f[q][1];

            for(int j=0;j<g[p].size();j++) {

                int k=g[p][j];

                if(k!=fa && k!=q) {

                    tmp += min(f[k][0],f[k][1]);

                }

            }

            f[p][0]=min(f[p][0],tmp);

        }

    }

}

signed main() {

    scanf("%lld",&n);

    for(int i=1;i<n;i++) {

        scanf("%lld%lld",&t1,&t2);

        g[t1].push_back(t2);

        g[t2].push_back(t1);

    }

    dfs(1);

    cout<<min(f[1][0],f[1][1])<<endl;

}

巴特西

[USACO08JAN] 手机网络 - 树形dp

最新文章

热门文章