1.txt

中南赛区ACM竞赛题 这题可以用Dijkstra的算法做,但是dfs的时间加减枝后也只有15ms,我用的是dfs. 就是遍历每种可行的树,要求每个棵树上的节点的地位都在maxdw,mindw,(最

题目意思是有一个树,树上的每个节点有一个价格,
要求以最小的价格买到根节点.
节点有子节点,如果子节点被购买则可以以另外一个价格购买(兑换)此节点.(此价格一般小于原来购买所要的价格)
且每个节点有个地位值,发生兑换的子树上所有节点两两之间的地位值之差最大不能超过 M .
输入:
n m   (共n个节点,地位差最大值m,以下n行,每行为Ni)
  moni d t (购买第i个节点的钱moni,地位d,有t个节点是他的子节点,以下t行)
     j monj (j是i的子节点,如果拥有j只要monj钱能获得i)
     …………（j-1行）
  …………(n-1行)
输出:
ans  (最小能换到的钱)
分析:这题可以用Dijkstra的算法做,但是dfs的时间加减枝后也只有15ms,我用的是dfs.
就是遍历每种可行的树,要求每个棵树上的节点的地位都在maxdw,mindw,(最大地位,最小地位)的范围内.
       这两个值从根节点遍历的时候每经过一个节点都要修正,回溯的时候也要复原.
因为每棵树的每个节点所算出的最小遍历值下次遍历此节点的时候不会改变,所以可以保存起来,就不用重复计算. (最优化减枝)
        (有可能会因为地位范围的改变而改变,但是肯定不能大于原来小地位范围算出的值(易证小地位范围肯定属于大地位范围),所以也要遍历,但是每次保存最小的做减枝就行)
且<获得子节点所要花的钱>最大不能超过<买父节点花的钱>减去<拥有子节点还要花的钱>. (可行性减枝)
这样搜索就可以求解了.要注意判环和判负.
附上程序.
#include <stdio.h>
#include <string.h>
int dw1,dw2,a[101][101],n,m,d[101],ans;
int minm(int a,int b)
{
if (a>b) return b;
else return a;
}
int maxm(int a,int b)
{
if (a>b) return a;
else return b;
}
int mn(int now,int mx)
{
int i,t,twei1,twei2;
if (mx<0) return 200000000;
for (i=1;i<=n;i++)
{
  if (a[now]!=-1&&i!=now)
  {
   twei1=dw1;twei2=dw2;
   dw1=maxm(d[now]-m,dw1);
   dw2=minm(d[now]+m,dw2);
   if (dw1<=dw2&&(dw1<=d&&dw2>=d))
   {
    t=a[now]+mn(i,minm(mx,a[now][now])-a[now]);
    if (t<a[now][now])
     a[now][now]=t;
   }
   dw1=twei1;dw2=twei2;
  }
}
return a[now][now];
}
int main()
{
int i,j,t1,t2,ja;
//freopen("e:\\text.txt","r",stdin);
scanf("%d%d",&m,&n);
memset(a,-1,sizeof(a));
for (i=1;i<=n;i++)
{
  scanf("%d%d%d",&a,&d,&ja);
  for (j=1;j<=ja;j++)
  {
   scanf("%d%d",&t1,&t2);
   a[t1]=t2;
  }
}
dw1=d[1]-m;dw2=d[1]+m;
ans=mn(1,200000000);
printf("%d\n",ans);
return 0;
}