HDU - 5036 Explosion

HDU - 5036 Explosion

Problem Description Everyone knows Matt enjoys playing games very much. Now, he is playing such a game. There are N rooms, each with one door. There are some keys(could be none) in each room corresponding to some doors among these N doors. Every key can open only one door. Matt has some bombs, each of which can destroy a door. He will uniformly choose a door that can not be opened with the keys in his hand to destroy when there are no doors that can be opened with keys in his hand. Now, he wants to ask you, what is the expected number of bombs he will use to open or destroy all the doors. Rooms are numbered from 1 to N.
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個房間被炸開都會導致這個房間被打開。那麼炸一次這個房間被打開的概率即為kn。也就意味著為了把這個房間打開的期望炸的次數為nk。全部加起來後除以n即可。bitset優化。

#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;
}