Sephiroth's boring days!!!

Love just for you.

动态规划-皇宫看守

【问题描述】

太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。

皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。

帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。

【数据输入】

输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树,描述如下:

第1行 n,表示树中结点的数目。

第2行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i(0<i<=n),在该宫殿安置侍卫所需的经费k,该边的儿子数m,接下来m个数,分别是这个节点的m个儿子的标号r1,r2,...,rm。

对于一个n(0 < n <= 1500)个结点的树,结点标号在1到n之间,且标号不重复。

【数据输出】

输出到OUTPUT.TXT文件中。输出文件仅包含一个数,为所求的最少的经费。

 

 

 

 

 

 

输入数据示例  输出数据示例

      25

【分析】

分别用f[i][0]表示i点放看守,f[i][1]表示i点不放看守i点被儿子监视,f[i][2]表示i点不放看守i点被父节点监视三个情况下的最小费用。

f[i][0]=所有子节点t的f[t][0],f[t][1],f[t][2]中最小的一个的合+k[i]

f[i][1]=某个子节点放看守+其他节点的f[t][0],f[t][1]中最小的一个的合

f[i][2]=所有子节点的f[t][1]的合

  1: #include <stdio.h>
  2: #include <iostream>
  3: #define maxn 1510
  4: #define MAXINT 10000000
  5: using namespace std;
  6: 
  7: int son[maxn][maxn];
  8: int m[maxn];
  9: int n,x;
 10: int k[maxn];
 11: int tem[maxn];
 12: bool ro[maxn];
 13: int v;
 14: int f[maxn][3];
 15: 
 16: void dp(int x)
 17: {
 18:     if (f[x][0]) return;
 19:     for (int i=1;i<=m[x];++i)
 20:     {
 21:         int t=son[x][i];
 22:         dp(t);
 23:         f[x][0]+=min(f[t][0],min(f[t][1],f[t][2]));
 24:         f[x][2]+=f[t][1];
 25:     }
 26:     f[x][0]+=k[x];
 27:     memset(tem,0,sizeof(tem));
 28:     int tot=0;
 29:     for (int i=1;i<=m[x];++i)
 30:     {
 31:         int t=son[x][i];
 32:         tem[i]=min(f[t][0],f[t][1]);
 33:         tot+=tem[i];
 34:     }
 35:     f[x][1]=MAXINT;
 36:     for (int i=1;i<=m[x];++i)
 37:     {
 38:         int t=son[x][i];
 39:         if (tot-tem[i]+f[t][0]<f[x][1]) f[x][1]=tot-tem[i]+f[t][0];
 40:     }
 41: }
 42: 
 43: int main()
 44: {
 45:     freopen("guard.in","r",stdin);
 46:     freopen("guard.out","w",stdout);
 47:     
 48:     scanf("%d",&n);
 49:     for (int i=1;i<=n;++i)
 50:     {
 51:         scanf("%d",&x);
 52:         scanf("%d%d",&k[x],&m[x]);
 53:         for (int j=1;j<=m[x];++j)
 54:         {
 55:             scanf("%d",&son[x][j]);
 56:             ro[son[x][j]]=1;
 57:         }
 58:     }
 59:     for (int i=1;i<=n;++i)
 60:         if (!ro[i])
 61:         {
 62:             v=i;
 63:             break;
 64:         }
 65:     //for (int i=1;i<=n;++i)
 66:     //f[i][2]=f[i][1]=MAXINT;
 67:     dp(v);
 68:     printf("%d\n",min(f[v][0],f[v][1]));
 69:     return 0;
 70: }
 71: 

posted on 2010-09-02 19:58 Sephiroth Lee 阅读(487) 评论(1)  编辑 收藏 引用 所属分类: 信息奥赛

Feedback

# re: 动态规划-皇宫看守 2011-05-03 16:54 dasfdf

jhsajkldfasjkl;dfdsa  回复  更多评论   



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


free counters