HDU 5036 Explosion

题目链接

思路：对于每个点，只要考虑哪些炸掉能到他的个数cnt，那么他对应的期望就是1 / cnt，然后所以期望的和就是答案，用bitset来维护

代码：

#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;

const int N = 1005;
int t, n;
bitset<N> bs[N];

int main() {
	int cas = 0;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			bs[i].reset();
			bs[i][i] = true;
		}
		int num, v;
		for (int i = 0; i < n; i++) {
			scanf("%d", &num);
			while (num--) {
				scanf("%d", &v); v--;
				bs[i][v] = true;
			}
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (bs[j][i])
					bs[j] |= bs[i];
		double ans = 0;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < n; j++)
				if (bs[j][i]) cnt++;
			ans += 1.0 / cnt;
		}
		printf("Case #%d: %.5lf\n", ++cas, ans);
	}
	return 0;
}

HDU 5036 Explosion（北京网络赛E题）