99久久综合狠狠综合久久止,欧美一区二区三区久久综,久久亚洲国产中v天仙www

pku 2908

2009年8月3日

題目鏈接：PKU 2908 Quantum

分類(lèi)：bfs+堆優(yōu)化

題目分析與算法原型
這道題總的來(lái)說(shuō)是一個(gè)廣度優(yōu)先搜索，但是需要用最小堆進(jìn)行優(yōu)化（如果不用堆，呵呵，我沒(méi)試過(guò)，不過(guò)8成會(huì)TLE），每次從隊(duì)列中取隊(duì)頭元素進(jìn)行擴(kuò)展（由于是最小堆，保證了每次取出的元素是當(dāng)前中花費(fèi)最小的），需要注意的是，一個(gè)已經(jīng)入過(guò)隊(duì)列的元素，還可以再入隊(duì)列，只要此時(shí)他的花費(fèi)比上次入隊(duì)列時(shí)小就行，還要注意的一點(diǎn)是結(jié)束條件應(yīng)該是當(dāng)且隊(duì)列彈出的隊(duì)頭元素的關(guān)鍵值等于目標(biāo)關(guān)鍵值，此時(shí)可以結(jié)束搜索，因?yàn)榧词挂院笤俅斡龅皆撽P(guān)鍵值的元素其花費(fèi)肯定比現(xiàn)在的大，因?yàn)槊看螐年?duì)頭開(kāi)始擴(kuò)展的元素都會(huì)比擴(kuò)展他的父親元素的花費(fèi)大，我就是這個(gè)退出條件沒(méi)搞好結(jié)果貢獻(xiàn)了n次的WA.............

Code:

1

#include<stdio.h>
2

#include<string.h>
3

char beg[25],end[25];
4

int n,l,p,w,count,mincost[1200000];
5

bool flag[1200000],finish;
6

struct node
7

{
8

int cost,num;
9

char s[25];
10

}queue[1200000];
11

struct caozuo
12

{
13

char s[25];
14

int cost;
15

}op[35];
16

int 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

}
22

void down_min_heap(int n,int h)//n表示堆元素的個(gè)數(shù)，從0開(kāi)始編號(hào),從h開(kāi)始往下調(diào)整
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

}
39

void up_min_heap(int s) //s表示最后一個(gè)的編號(hào)
40

{
41

while (s>0&&queue[s].cost<queue[(s-1)/2].cost) //從s開(kāi)始往上調(diào)整
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

}
49

void 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

}
57

node 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

}
65

void 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

}
93

int 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

}
111

int 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 閱讀(181) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

pku 2908

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜