[关闭]
@zzzc18 2017-05-12T12:05:31.000000Z 字数 3927 阅读 572

2017.5.3 Catch

TEST


柠檬当上了警察局长!

( ( catch .pas/c/cpp)

【题目描述】

Lemon 因为偶然的原因,当上了警察局长。而一上任,他就碰到了个大麻烦:追捕周克华。
周克华是人尽皆知的抢劫杀人犯,而就在几天前,他在 Lemon 辖区内的银行门口,枪杀了
一名储户后逃之夭夭。Lemon 知道,如果他抓不住周克华,他的警察局长恐怕就当不下去了。
为了能继续当他的警察局长,Lemon 决定倾警察局之物力全力追捕。Lemon 的辖区可以表示
为一张边上带权的无向图。银行位于结点 1。
Lemon 仔细研究周克华的案底后得出以下结论:
首先,周克华拥有极强的反侦查能力,因此,他深知不走回头路的重要性。他永远不会访问
任何一个结点两次。
其次,周克华深知多走一分钟路就多一分钟暴露的危险,而且他之前已经完全摸清了辖区的
地形,因此他总是走最短路,也就是,他访问任何一个结点时,走的路线都是从银行到这里
的最短路。为了简化题目,我们保证从银行(结点 1)到任何一个结点的最短路都是唯一的。
再次,周克华知道,为了尽可能远离案发现场,他必须不停的运动。也就是说,只要有相邻
的结点能满足“不走回头路、只走最短路”的前提,他一定会移动。如果有多个相邻结点可
供选择,他会随机等概率选择一个作为他的移动目标。如果没有结点满足这一要求,那么周
克华就会选择遁入深山之中,而可以想象在距离案发现场十万八千里的山区里抓捕周克华的
难度,所以一旦周克华遁入山中,也就意味着 Lemon 的抓捕行动失败了。
Lemon 分析出了以上结论后决定,只能在结点上布置警察,实施埋伏抓捕。但是,周克华的
身体素质、反侦查能力和使用武器技术都十分优秀,因此,即使周克华遇到了埋伏,也有一
定几率杀害所有参与埋伏的警察后逃脱。当然,随着埋伏的警察的数目的增多,逃脱几率会
减小。如果逃脱成功,周克华会像什么都没发生一样,继续按上文所述的方式行动。
注意,周克华一旦到达一个结点,埋伏在那里的警察会立即实施抓捕,只有周克华逃脱了在
当前结点的抓捕后才能进行下一步行动(遁入群山或继续移动),包括结点 1,也就是周克
华需要先逃脱结点 1 的埋伏才能走出他的第一步。
Lemon 知道,他的设置警力方式决定了追捕成功的概率。他现在已经知道了他的辖区地图以
及在不同地点设置不同数量的警力能成功抓捕周克华的概率,Lemon 现在想要找到一个尽量
优的方式设置警力,因此求助于你。你能告诉 Lemon 在最优的设置下,抓捕成功概率是多
少吗? Lemon 到时或许会把高额的悬赏分给你一部分的哦~

【输入格式】

输入文件第一行包含两个数 N,M,分别表示辖区里的结点数目和边的数目。
接下来 M 行,每行 3 个数 a,b,c,表示结点 a 和 b 之间有一条权值为 c 的无向边。
接下来一个数 S,表示可以参与埋伏的警察个数。
接下来 N 行,每行 S 个数,第 i 行第 j 个数 Pij 表示在结点 i 埋伏 j 个警察抓捕成功的概率。
注意,如果不埋伏任何警察,那么显然绝不可能成功抓住周克华。

【输出格式】

输出文件仅包含一个实数,保留到 4 位小数,表示在最优警力设置下,抓捕成功的概率。

【输入样例】

4 4
1 2 1
1 3 2
2 4 3
3 4 1
2
0.01 0.1
0.5 0.8
0.5 0.8
0.7 0.9

【输出样例】

0.6000

Solution

//最开始把每个点的概率算出来再一块01背包,显然不对,然而还是过了一个点.....

正解:
Step1:预处理出从1为起点的最短路,构建一个新图,只包含最短路(因为他非最短路不走嘛)
Step2:树形DP,在DP时每个节点以其子节点为物品做一次01背包

  1. ans:total answer;dp:single dot answer;tmp:bags for sons
  2. for(i=h1[x];i;i=e1[i].next){
  3. for(j=0;j<=police;j++) tmp[j]=0;
  4. for(j=0;j<=police;j++){
  5. for(k=0;k<=j;k++){
  6. tmp[j]=max(tmp[j],dp[j-k]+ans[e1[i].to][k]);
  7. }
  8. }
  9. for(j=0;j<=police;j++)
  10. dp[j]=max(dp[j],tmp[j]);
  11. }

Step3:DP的同时把概率考虑进去(size为当前节点的子节点数)

  1. for(i=0;i<=police;i++)
  2. dp[i]/=size[x];
  3. for(i=0;i<=police;i++){
  4. for(j=0;j<=i;j++){
  5. ans[x][i]=max(ans[x][i],dp[i-j]+(1-dp[i-j])*node[x].num[j]);
  6. }
  7. }

  1. #include<cstdio>
  2. #include<queue>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define MAXM 20005
  6. #define MAXN 205
  7. using namespace std;
  8. int n,m,edge_num,e_num;
  9. int police;
  10. struct E{
  11. int next,to,val;
  12. }edge[MAXM*2],e1[2*MAXM];
  13. int dis[MAXN];
  14. queue<int> que;bool inque[MAXN];
  15. int head[MAXN],h1[MAXN];
  16. struct N{
  17. double num[MAXN];
  18. double ZH;
  19. }node[MAXN];
  20. int size[MAXN];
  21. double ans[MAXN][MAXN],dp[MAXN],tmp[MAXN];
  22. void addedge(int x,int y,int z){
  23. edge[++edge_num].next=head[x];
  24. edge[edge_num].to=y;
  25. edge[edge_num].val=z;
  26. head[x]=edge_num;
  27. }
  28. void add(int x,int y,int z){
  29. e1[++e_num].next=h1[x];
  30. e1[e_num].to=y;
  31. e1[e_num].val=z;
  32. h1[x]=e_num;
  33. }
  34. void SPFA(){
  35. memset(dis,0x7f,sizeof(dis));
  36. dis[1]=0;
  37. que.push(1);
  38. while(!que.empty()){
  39. int fro=que.front();que.pop();inque[fro]=0;
  40. int i;
  41. for(i=head[fro];i;i=edge[i].next){
  42. if(dis[edge[i].to]>dis[fro]+edge[i].val){
  43. dis[edge[i].to]=dis[fro]+edge[i].val;
  44. if(!inque[edge[i].to]){
  45. inque[edge[i].to]=1;
  46. que.push(edge[i].to);
  47. }
  48. }
  49. }
  50. }
  51. }
  52. void newmap(int x,int fa){
  53. int i;
  54. for(i=head[x];i;i=edge[i].next){
  55. if(edge[i].to==fa) continue;
  56. if(dis[x]+edge[i].val==dis[edge[i].to]){
  57. add(x,edge[i].to,edge[i].val);
  58. newmap(edge[i].to,x);
  59. }
  60. }
  61. }
  62. void DFS(int x,int fa){
  63. int i;
  64. for(i=h1[x];i;i=e1[i].next){
  65. size[x]++;
  66. DFS(e1[i].to,x);
  67. }
  68. }
  69. void DP(int x){
  70. int i,j,k;
  71. if(!size[x]){
  72. for(i=0;i<=police;i++)
  73. ans[x][i]=node[x].num[i];
  74. return;
  75. }
  76. for(i=h1[x];i;i=e1[i].next) DP(e1[i].to);
  77. for(int u=0;u<=police;u++)dp[u]=0;
  78. for(i=h1[x];i;i=e1[i].next){
  79. for(j=0;j<=police;j++) tmp[j]=0;
  80. for(j=0;j<=police;j++){
  81. for(k=0;k<=j;k++){
  82. tmp[j]=max(tmp[j],dp[j-k]+ans[e1[i].to][k]);
  83. }
  84. }
  85. for(j=0;j<=police;j++)
  86. dp[j]=max(dp[j],tmp[j]);
  87. }
  88. for(i=0;i<=police;i++)
  89. dp[i]/=size[x];
  90. for(i=0;i<=police;i++){
  91. for(j=0;j<=i;j++){
  92. ans[x][i]=max(ans[x][i],dp[i-j]+(1-dp[i-j])*node[x].num[j]);
  93. }
  94. }
  95. }
  96. void solve(){
  97. newmap(1,0);
  98. DFS(1,0);
  99. DP(1);
  100. double ANS=0;
  101. for(int i=0;i<=police;i++){
  102. ANS=max(ANS,ans[1][i]);
  103. }
  104. printf("%.4lf\n",ANS);
  105. }
  106. int main(){
  107. freopen("catch.in","r",stdin);
  108. freopen("catch.out","w",stdout);
  109. scanf("%d%d",&n,&m);
  110. int i;
  111. int a,b,c;
  112. for(i=1;i<=m;i++){
  113. scanf("%d%d%d",&a,&b,&c);
  114. addedge(a,b,c);
  115. addedge(b,a,c);
  116. }
  117. scanf("%d",&police);
  118. int j;
  119. for(i=1;i<=n;i++){
  120. for(j=1;j<=police;j++){
  121. scanf("%lf",&node[i].num[j]);
  122. }
  123. }
  124. SPFA();
  125. solve();
  126. return 0;
  127. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注