安排警卫题解

题目大意：有一个由N个节点构成的树，在每个节点安排警卫的花费都不同，只有在某个节点布置警卫，或者在其某个相邻节点布置警卫，才可以保证这个节点安全。求：要让所有节点都安全，最少的花费是多少。

容易看出问题的最优子结构性质，因此考虑树形动态规划。那么，要如何表示状态呢？本人用f[x][0]表示在x节点不放置警卫，使以x为根的子树安全的最小花费；f[x][1]表示在x放置警卫，使以x为根的子树安全的最小花费。不过，这个状态表示不能包括下面这个情形：
[1](10)------[2](20)------[3](30)------[4](5)
方括号内是节点编号，圆括号内是安排警卫的费用， 此时的最优解是15,而本人的解是25.

因此，增加一个状态，用f[x][2]表示不再x安排警卫，在x的父亲节点安排。

由于转移方程要考虑多种情况，较为复杂，读者请直接看代码。

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define BY_FATHER 0    //自己不安排警卫，父亲节点安排
#define BY_CHILD 1    //自己不安排，至少一个儿子安排
#define BY_ITSELF 2    //自己安排警卫
#define MAXN 730
#define INF 100000000

typedef struct node
{
   int v;
   struct node *next;
}node;

node *first[MAXN];
long cost[MAXN];
int father[MAXN];
int N;

long f[MAXN][3];

inline void addedge(int u,int v)
{
   node *p;
   p = malloc(sizeof(node));
   p->next = first[u];
   first[u] = p;
   p->v = v;
}

void init()
{
   int j,i,m,v;
   scanf("%d\n",&N);
   for(j = 0;j < N;j ++)
   {
       scanf("%d",&i);
       scanf("%ld%d",&cost[i],&m);
       while(m --)
       {
           scanf("%d",&v);
           father[v] = i;
           addedge(i,v);
       }
   }
}

inline long getmin(long a,long b)
{
   if(a < b)    return a;
   return b;
}

long min3(long a,long b,long c)
{
   return getmin(a,getmin(b,c));
}

void solve(int x)
{
   node *p;
   if(first[x] == NULL)   //x is leaf
   {
       f[x][BY_FATHER] = 0;
       f[x][BY_ITSELF] = cost[x];
       f[x][BY_CHILD] = INF;  //no child
       return;
   }
   int flag = 0;   //记录是否至少有一个儿子安排
   f[x][BY_ITSELF] = cost[x];
   for(p = first[x];p != NULL;p = p->next)
   {
       solve(p->v);
       f[x][BY_ITSELF] += min3(f[p->v][BY_FATHER],f[p->v][BY_ITSELF],f[p->v][BY_CHILD]);
       if(first[p->v] == NULL)    //儿子是叶子节点的特殊情况
       {
           f[x][BY_FATHER] += f[p->v][BY_ITSELF];
           f[x][BY_CHILD] += f[p->v][BY_ITSELF];
           flag = 1;
       }
       else
       {
           f[x][BY_FATHER] += getmin(f[p->v][BY_CHILD],f[p->v][BY_ITSELF]);
           if(f[p->v][BY_ITSELF] <= f[p->v][BY_CHILD])
           {
               flag = 1;
               f[x][BY_CHILD] += f[p->v][BY_ITSELF];
           }
           else
               f[x][BY_CHILD] += f[p->v][BY_CHILD];
       }
   }
   if(!flag)
   {
       long min = INF;
       for(p = first[x];p != NULL;p = p->next)
           if(f[p->v][BY_ITSELF] - f[p->v][BY_CHILD] < min)        min = f[p->v][BY_ITSELF] - f[p->v][BY_CHILD];
       f[x][BY_CHILD] += min;
   }
}

void debug()
{
   int x;
   for(x = 1;x <= N;x ++)
       fprintf(stderr,"%3d%4ld%4ld%4ld\n",x,f[x][0],f[x][1],f[x][2]);
}

int main()
{
   freopen("security.in","r",stdin);
   freopen("security.out","w",stdout);
   init();
   int x;
   for(x = 1;x <= N && father[x] != 0;x ++);   //find root node x
   solve(x);
   printf("%ld\n",getmin(f[x][BY_CHILD],f[x][BY_ITSELF]));
   //debug();
   fclose(stdout);
   return 0;
}