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

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