pku 2908

2009年8月3日

题目链接：PKU 2908 Quantum
  
分类：bfs+堆优化

题目分析与算法原型
         这道题总的来说是一个广度优先搜索，但是需要用最小堆进行优化（如果不用堆，呵呵，我没试过，不过8成会TLE），每次从队列中取队头元素进行扩展（由于是最小堆，保证了每次取出的元素是当前中花费最小的），需要注意的是，一个已经入过队列的元素，还可以再入队列，只要此时他的花费比上次入队列时小就行，还要注意的一点是结束条件应该是当且队列弹出的队头元素的关键值等于目标关键值，此时可以结束搜索，因为即使以后再次遇到该关键值的元素其花费肯定比现在的大，因为每次从队头开始扩展的元素都会比扩展他的父亲元素的花费大，我就是这个退出条件没搞好结果贡献了n次的WA.............

Code:

  1#include<stdio.h>
  2#include<string.h>
  3char beg[25],end[25];
  4int n,l,p,w,count,mincost[1200000];
  5bool flag[1200000],finish;
  6struct node
  7{
  8    int cost,num;
  9    char s[25];
 10}queue[1200000];
 11struct caozuo
 12{
 13    char s[25];
 14    int cost;
 15}op[35];
 16int cal(char ss[])
 17{
 18    int i,res=0;
 19    for(i=0;i<l;i++)res+=(ss[i]-'0')<<(l-1-i);
 20    return res;
 21}
 22void down_min_heap(int n,int h)//n表示堆元素的个数，从0开始编号,从h开始往下调整
 23{
 24    int i=h,j=2*i+1;
 25    node temp=queue[i];
 26    while(j<n)
 27    {
 28        if(j<n-1&&queue[j].cost>queue[j+1].cost)j++;//若右孩子存在，且右孩子比较小，取右
 29        if(temp.cost<queue[j].cost)break;
 30        else
 31        {
 32            queue[i]=queue[j];
 33            i=j;
 34            j=2*i+1;
 35        }
 36    }
 37    queue[i]=temp;
 38}
 39void up_min_heap(int s)    //s表示最后一个的编号
 40{
 41    while (s>0&&queue[s].cost<queue[(s-1)/2].cost)     //从s开始往上调整
 42    { 
 43        node tt=queue[s];
 44        queue[s]=queue[(s-1)/2];
 45        queue[(s-1)/2]=tt;
 46        s=(s-1)/2; 
 47    }
 48}
 49void push(int x,int cost,char s[])
 50{
 51    queue[count].num=x;
 52    queue[count].cost=cost;
 53    strcpy(queue[count].s,s);
 54    count++;
 55    up_min_heap(count-1);
 56}
 57node pop()
 58{
 59    node res=queue[0];
 60    queue[0]=queue[count-1];
 61    count--;
 62    down_min_heap(count,0);
 63    return res;
 64}
 65void handle(int num,node x,int goal,int *ans)
 66{
 67    int i,k;
 68    node y=x;
 69    if(y.num==goal)
 70    {
 71        finish=true;
 72        *ans=y.cost;
 73        return ;
 74    }
 75    for(i=0;i<l;i++)
 76    {
 77        if(op[num].s[i]=='F')
 78        {
 79            if(y.s[i]=='0')y.s[i]='1';
 80            else y.s[i]='0';
 81        }
 82        else if(op[num].s[i]=='S')y.s[i]='1';
 83        else if(op[num].s[i]=='C')y.s[i]='0';
 84    }
 85    k=cal(y.s);
 86    if(!flag[k]||(flag[k]&&op[num].cost+y.cost<mincost[k]))
 87    {
 88        flag[k]=true;
 89        mincost[k]=op[num].cost+y.cost;
 90        push(k,op[num].cost+y.cost,y.s);
 91    }
 92}
 93int bfs(char a[],char b[])
 94{
 95    int r1=cal(a),r2=cal(b),i,ans;
 96    node tt;
 97    queue[0].num=r1;
 98    queue[0].cost=0;
 99    strcpy(queue[0].s,a);
100    count=1;
101    flag[r1]=true;
102    mincost[r1]=0;
103    while(count>0)
104    {
105        tt=pop();
106        for(i=0;i<p&&!finish;i++)handle(i,tt,r2,&ans);
107        if(finish)return ans;
108    }
109    return -1;
110}
111int main()
112{
113    int i;
114    scanf("%d",&n);
115    while(n--)
116    {
117        scanf("%d%d%d",&l,&p,&w);
118        for(i=0;i<p;i++)scanf("%s %d",op[i].s,&op[i].cost);
119        for(i=0;i<w;i++)
120        {
121            scanf("%s %s",beg,end);
122            memset(flag,false,sizeof(flag));
123            finish=false;
124            int res=bfs(beg,end);
125            if(res==-1)printf("NP");
126            else printf("%d",res);
127            if(i<w-1)printf(" ");
128        }
129        printf("\n");
130    }
131    return 1;
132}
133
134
135
136

posted on 2009-08-03 10:32 蜗牛也Coding 阅读(212) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜