[CQOI2009]叶子的染色

传送门：https://www.luogu.org/problemnew/show/P3155

一道挺水的树形dp题，然后我因为一个挺智障的问题debug了一晚上……

嗯……首先想，如果一个点的颜色和他的儿子相同，那么删去他儿子的颜色显然不影响，而且更符合最优解，然后我们dp时就从子树开始往上找，将儿子的状态转移给父亲时，就将儿子的颜色删去。

所以开一个dp[maxn][2]，

dp[i][0]表示节点i染成黑色，以i为根的子树最少需要染色的点数。

dp[i][1]节点i染成白色，以i为根的子树最少需要染色的点数。

所以

dp[i][0] = 1+∑min(dp[j][0] - 1, dp[j][1]) (j取遍i的儿子)
dp[i][1] = 1+∑min(dp[i][0], dp[i][1] - 1) (j取遍i的儿子)

然后直接贴代码

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<cctype>

 #include<vector>

 using namespace std;

 #define enter printf("\n")

 #define space printf(" ")

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn = 5e4 + ;

 //const int maxm = 1e4 + 5;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch))

     {

         ans = ans *  + ch - ''; ch = getchar();

     }

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar('' + x % );

 }

 int n, m, c[maxn];

 vector<int> v[maxn];

 bool vis[maxn];

 int dp[maxn][];        //0:染成黑色，1：染成白色

 void dfs(int now)

 {

     vis[now] = ;

     if(now <= n) return;

     dp[now][] = ; dp[now][] = ;

     for(int i = ; i < (int)v[now].size(); ++i)

     {

         if(!vis[v[now][i]])

         {

             dfs(v[now][i]);

             dp[now][] += min(dp[v[now][i]][] - , dp[v[now][i]][]);

             dp[now][] += min(dp[v[now][i]][] - , dp[v[now][i]][]);

         }

     }

 }

 int main()

 {

     m = read(), n = read();

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

     {

         c[i] = read();

         dp[i][c[i]] = ; dp[i][c[i] ^ ] = INF;

     }

     for(int i = ; i < m; ++i)

     {

         int a = read(), b = read();

         v[a].push_back(b); v[b].push_back(a);

     }

     dfs(n + );

     write(min(dp[n + ][], dp[n + ][])); enter;

     return ;

 }

好了，现在讲讲为啥写代码10分钟，debug数小时。

其实就是对于无向图所走边的判重问题。

众所周知，用一个vis数组就能解决，然后因人而异在dfs开头标记或是在if(!vis[i]) 后 vis[j] = 1 (j为i的孩子).

然后我就是第二种写法。

然而

这会错

因为

根节点

没有

打！上！标！记！

所以，请务必vis[n + 1] = 1后，在dfs(n + 1)…………

巴特西

[CQOI2009]叶子的染色

最新文章

热门文章