Input The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.
In the first line of each test case, there is an integer N (N<=1000) indicating the number of rooms.
The following N lines corresponde to the rooms from 1 to N. Each line begins with an integer k (0<=k<=N) indicating the number of keys behind the door. Then k integers follow corresponding to the rooms these keys can open.
Output For each test case, output one line "Case #x: y", where x is the case number (starting from 1), y is the answer which should be rounded to 5 decimal places.
Sample Input
2 3 1 2 1 3 1 1 3 0 0 0
Sample Output
Case #1: 1.00000 Case #2: 3.00000
Source 2014 ACM/ICPC Asia Regional Beijing Online
题意：n个房间，每个房间都有若干个钥匙打开其他的门，如果手上没有钥匙可以选择等概率随机选择一个门炸开，求用炸弹数的期望。
思路：每个房间期望都是可加的。 单独考虑一个房间，如果有k个房间被炸开都会导致这个房间被打开。那么炸一次这个房间被打开的概率即为
#include#include #include #include #include using namespace std; const int maxn = 1005; bitset a[maxn]; int main() { int t, cas = 1; int n; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) { a[i].reset(); a[i][i] = 1; } int c, x; for (int i = 0; i < n; i++) { scanf("%d", &c); while (c--) { scanf("%d", &x); a[i][--x] = 1; } } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[j][i]) a[j] |= a[i]; double ans = 0; for (int i = 0; i < n; i++) { c = 0; for (int j = 0; j < n; j++) if (a[j][i]) c++; ans += 1.0 / c; } printf("Case #%d: %.5lf\n",cas++,ans); } return 0; }