1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| #include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#define REP(i, k, n) for(int i = k; i < n; i++)
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
struct SCC {
int n;
vector<vector<int> > g, rg, ng, scc;
vector<int> res;
bool used[105];
SCC(int _n) {
n = _n;
g.resize(n); rg.resize(n); scc.resize(n); res.resize(n);
}
void add(int i, int j) {
g[i].push_back(j);
rg[j].push_back(i);
}
vector<int> vs;
void dfs(int v) {
used[v] = true;
rep(i, g[v].size()) {
if(!used[ g[v][i] ]) dfs(g[v][i]);
}
vs.push_back(v);
}
void rdfs(int v, int k) {
used[v] = true;
res[v] = k;
scc[k].push_back(v);
rep(i, rg[v].size()) {
if(!used[ rg[v][i] ]) rdfs(rg[v][i], k);
}
}
void ng_make(int k) {
ng.resize(k);
rep(i, n) {
set<int> S;
rep(j, g[i].size()) {
int to = g[i][j];
if(res[i] == res[to]) continue;
if(S.find(res[to]) != S.end()) continue;
ng[res[i]].push_back(res[to]);
S.insert(res[to]);
}
}
}
int build() {
memset(used, 0, sizeof(used));
rep(i, n) {
if(!used[i]) dfs(i);
}
memset(used, 0, sizeof(used));
int k = 0;
for(int i = vs.size()-1; i >= 0; i--) {
if(!used[vs[i]]) rdfs(vs[i], k++);
}
ng_make(k);
return k;
}
};
int main() {
int n;
while(cin >> n && n) {
vector<double> v(n);
SCC scc(n);
rep(i, n) {
int x;
cin >> v[i] >> x;
rep(j, x) {
int a;
cin >> a;
a--;
scc.add(i, a);
}
}
int k = scc.build();
vector<vector<int> > g = scc.ng;
int cnt[105];
memset(cnt, 0, sizeof(cnt));
rep(i, k) {
rep(j, g[i].size()) {
cnt[g[i][j]]++;
}
}
double ans = 1.0;
rep(i, k) {
if(cnt[i] != 0) continue;
double t = 1.0;
rep(j, scc.scc[i].size()) {
int u = scc.scc[i][j];
t *= v[u];
}
ans *= (1.0 - t);
}
cout << fixed;
cout.precision(20);
cout << ans << endl;
}
return 0;
}
|