BZOJ 1415: [Noi2005]聪聪和可可

1415: [Noi2005]聪聪和可可

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1528 Solved: 903
[Submit][Status][Discuss]

Description

Input

数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

Output

输出1个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

Sample Input

【输入样例1】
4 3
1 4
1 2
2 3
3 4
【输入样例2】
9 9
9 3
1 2
2 3
3 4
4 5
3 6
4 6
4 7
7 8
8 9

Sample Output

【输出样例1】
1.500
【输出样例2】
2.167

HINT

【样例说明1】
开始时，聪聪和可可分别在景点1和景点4。
第一个时刻，聪聪先走，她向更靠近可可(景点4)的景点走动，走到景点2，然后走到景点3；假定忽略走路所花时间。
可可后走，有两种可能：
第一种是走到景点3，这样聪聪和可可到达同一个景点，可可被吃掉，步数为1，概率为。
第二种是停在景点4，不被吃掉。概率为。
到第二个时刻，聪聪向更靠近可可(景点4)的景点走动，只需要走一步即和可可在同一景点。因此这种情况下聪聪会在两步吃掉可可。
所以平均的步数是1* +2* =1.5步。

对于所有的数据，1≤N,E≤1000。
对于50%的数据，1≤N≤50。

Source

[Submit][Status][Discuss]

这道SB题调了一上午，就是个DAG的期望DP，连gauss都不用的，随便DP一发就好，就是智障了~~~

  1 #include <cstdio>
  2 #include <cstring>
  3  
  4 template <class T>
  5 inline T min(const T &a, const T &b)
  6 {
  7     return a < b ? a : b;
  8 }
  9  
 10 const int siz = 1005;
 11  
 12 int n, m;
 13 int a, b;
 14  
 15 int tot;
 16 int hd[siz];
 17 int to[siz << 1];
 18 int nt[siz << 1];
 19  
 20 int cnt[siz];
 21 int que[siz];
 22 int inq[siz];
 23 int dis[siz];
 24 int mov[siz][siz];
 25  
 26 double f[siz][siz];
 27  
 28 double search(int x, int y)
 29 {
 30     if (f[x][y] >= 0.0)
 31         return f[x][y];
 32      
 33     int t = mov[mov[x][y]][y];
 34      
 35     if (t == y)
 36         return f[x][y] = 1;
 37      
 38     f[x][y] = search(t, y);
 39      
 40     for (int i = hd[y]; i; i = nt[i])
 41         f[x][y] += search(t, to[i]);
 42      
 43     return f[x][y] = f[x][y] / cnt[y] + 1.0;
 44 }
 45  
 46 signed main(void)
 47 {
 48     scanf("%d%d", &n, &m);
 49     scanf("%d%d", &a, &b);
 50      
 51     for (int i = 1; i <= m; ++i)
 52     {
 53         int x, y; scanf("%d%d", &x, &y);
 54          
 55         ++cnt[x];
 56         ++cnt[y];
 57          
 58         nt[++tot] = hd[x], to[tot] = y, hd[x] = tot;
 59         nt[++tot] = hd[y], to[tot] = x, hd[y] = tot;
 60     }
 61      
 62     {
 63         for (int i = 1; i <= n; ++i)
 64         {
 65             memset(inq, 0x00, sizeof inq);
 66             memset(dis, 0x3f, sizeof dis);
 67              
 68             int l = 0, r = 0;
 69              
 70             dis[i] = 0;
 71             inq[i] = 1;
 72              
 73             mov[i][i] = i;
 74              
 75             for (int j = hd[i]; j; j = nt[j])
 76                 inq[to[j]] = dis[que[r++] = mov[i][to[j]] = to[j]] = 1;
 77              
 78             while (l != r)
 79             {
 80                 int u = que[l++]; 
 81                  
 82                 for (int j = hd[u]; j; j = nt[j])
 83                 {
 84                     if (!inq[to[j]])
 85                         inq[que[r++] = to[j]] = 1;
 86                          
 87                     if (dis[to[j]] > dis[u] + 1)
 88                         dis[to[j]] = dis[u] + 1, mov[i][to[j]] = mov[i][u];
 89                     else if (dis[to[j]] == dis[u] + 1)
 90                         mov[i][to[j]] = min(mov[i][to[j]], mov[i][u]);
 91                 }
 92             }
 93         }
 94     }
 95      
 96     for (int i = 1; i <= n; ++i)
 97     {
 98         for (int j = 1; j <= n; ++j)
 99             f[i][j] = -1.0;
100          
101         f[i][i] = 0.0;
102          
103         ++cnt[i];
104     }
105      
106     printf("%.3lf
", search(a, b));
107 }

@Author: YouSiki