刷题记录（NC51222 Strategic game，NC24953 Cell Phone Network （树的最小支配集））

NC51222 Strategic game

题目链接

关键点：

1、题目要求在一颗树上，在节点放置士兵，每个士兵可以占据当前点和其孩子的点，要求全部节点都被占据需要最少多少个士兵

2、对于每个节点，都有占或者不占，如果该节点不占，那么其孩子节点就必须得占，如果该节点占，那么其孩子可以选择占或者不占

3、设置dp[i][0]表示i点不占，dp[i][1]表示i点占

dp[i][0] += dp[k][1],k值i的孩子

dp[i][1] += min(dp[k][0], dp[k][1]);

4、初始化，dp[i][0] = 0(该点不占), dp[i][1] = 1（该点占）

5、答案为占或者不占中选出最小的

完整代码：

# include
using namespace std;
int n;
int f[1600][3];
vector<int> ve[1600];
void dfs(int x, int fa)
{
    f[x][0] = 1;//该点放士兵
    f[x][1] = 0;//该点不放士兵
    for (int i=0; isize(); i++)
    {
        int j = ve[x][i];
        if (j == fa) continue;
        dfs(j, x);
        f[x][0] += min(f[j][0], f[j][1]);
        f[x][1] += f[j][0];
    }
}
int main()
{
    int x, len, y;
    while (cin>>n)
    {
//         cout<<"3"<
//         memset(f, 0, sizeof(f));
        for (int i=1; i<=n; i++)
        {
            cin>>x;
            scanf(":(%d)", &len);
            for (int j=1; j<=len; j++)
            {
                cin>>y;
                ve[x].push_back(y);
                ve[y].push_back(x);
//                 cout<<"2"<
            }
        }
        dfs(0, 0);
        cout<<min(f[0][1], f[0][0])<
        for (int i=0; i
            ve[i].clear();
//         
    }
    return 0;
}

NC24953 Cell Phone Network （树的最小支配集）

题目链接

关键点：

1、该题和上题略有不同，该题为在一个节点上放置，且会占据其相邻的节点。

2、那么该点被覆盖，有可能是来自于父亲，也有可能是自己，还有是孩子（上题可以为父亲或者自己），那么设置状态dp[i][0]表示i点占据，dp[i][0]点不放，且i点被孩子覆盖，dp[i][2]表示i点不放，且i点被父亲覆盖

dp[i][0] += max(dp[k][0], dp[k][1], dp[k][2]);//i点放，那么其孩子可放可不放

dp[i][2] += max(dp[k][0], dp[k][1]);i点不放，那么其孩子就不可能出现被其父亲覆盖的情况出现

dp[i][1]表示至少要有一个孩子是放的，那么选择哪个孩子放？

计算出所有孩子的放与不放，如果存在该孩子放比该孩子不放来的个数少，那么就选择该孩子放，那么如果所有的孩子都为不放比放好，那么我们就选择相差最少的那个孩子改为放。

3、对于dp[i][1]分析出来的计算，我们先让dp[i][1] += min(dp[k][0], dp[k][1]),然后再来一个inc先初始化为最大值，然后再将其每次都等于min(dp[i][0] - dp[i][1]);等到所有的孩子均遍历一遍后，判断inc是否有为负数，有的话说明存在有一个孩子放比不放好，则inc = 0,那么就dp[i][1]就为其本身，如果是>=0,说明均为不放比放好，且inc此时已经为那个差值最小的差值了，dp[i][1] += inc即可

4、初始化，dp[i][0] = 1,（该点放了+1）

dp[i][1] = dp[i][2] = 0(该点不放)

完整代码：

# include
using namespace std;
int n;
int f[10000+10][3];
vector<int> ve[10000+10];
void dfs(int x, int fa)
{
    f[x][0] = 1;
    f[x][1] = 0;
    f[x][2] = 0;
    int inc = 0x3f3f3f;
    for (int i=0; isize(); i++)
    {
        int j = ve[x][i];
        if (j == fa) continue;
        dfs(j, x);
        f[x][0] += min(f[j][1], min(f[j][0], f[j][2]));
        f[x][2] += min(f[j][0], f[j][1]);
        f[x][1] += min(f[j][0], f[j][1]);
        inc = min(f[j][0]-f[j][1], inc);
    }
    if (inc<0)
        inc = 0;
    f[x][1] += inc;
}
int main()
{
    cin>>n;
    int x, y;
    while (cin>>x>>y)
    {    
        ve[x].push_back(y);
        ve[y].push_back(x);   
    }
    dfs(1, 0);
    cout<<min(f[1][0], f[1][1])<
    return 0;
}