To seek candies for Maomao, Dudu comes to a maze. There are nn rooms numbered from 11 to nn and mmundirected roads.
There are two kinds of rooms in the maze -- candy room and monster room. There is one candy in each candy room, and candy room is safe. Dudu can take the only candy away when entering the room. After he took the candy, this candy room will be empty. A empty room is also safe. If Dudu is in safe, he can choose any one of adjacent rooms to go, whatever it is. Two rooms are adjacent means that at least one road connects the two rooms.
In another kind of rooms, there are fierce monsters. Dudu can't beat these monsters, but he has a magic portal. The portal can show him a randomly chosen road which connects the current room and the other room.
The chosen road is in the map so Dudu know where it leads to. Dudu can leave along the way to the other room, and those monsters will not follow him. He can only use the portal once because the magic energy is not enough.
Dudu can leave the maze whenever he wants. That's to say, if he enters a monster room but he doesn't have enough energy to use the magic portal, he will choose to leave the maze immediately so that he can save the candies he have. If he leave the maze, the maze will never let him in again. If he try to fight with the monsters, he will be thrown out of the maze (never let in, of course). He remembers the map of the maze, and he is a clever guy who can move wisely to maximum the expection of candies he collected.
Maomao wants to know the expected value of candies Dudu will bring back. Please tell her the answer. He will start his adventure in room 1, and the room 1 is always a candy room. Since there may be more than one road connect the current room and the room he wants to go to, he can choose any of the roads.
Input
First line a integer tt, means tt cases. 1 \le t \le 51≤t≤5
For each case:
First line 3 integer nn, mm, kk, nn means the number of rooms, mm means the number of roads, kk means the number of monster rooms. 1 \le n \le 1000001≤n≤100000, n-1 \le m \le 2*nn−1≤m≤2∗n, 0 \le k \le n0≤k≤n
Next mm lines, for each line there are two integer aa and bb, separated by a space, means there is a road between aaand bb. There may be repeated edges, but won't be self loop. 1 \le a,b \le n1≤a,b≤n
In the last line there are kk distinct numbers, the ii-th number x_ixi means the number of the ii-th monster room is x_ixi, and room 1 won't be monster room. 1 \le i \le k1≤i≤k
Output
For each case output a real number. The absolute error of the answer should not exceed 10^{-6}10−6.
本题答案不唯一，符合要求的答案均正确
样例输入
2 7 6 2 1 2 1 3 2 5 2 4 3 6 4 7 2 3 7 7 2 1 2 1 3 2 5 2 4 3 6 4 7 2 4 2 3
样例输出
2.000000 2.250000
题意：就是给一张n个点，m条边的图，可能有重边，图中只有两种房间，一种有怪物，其他的是糖果屋，并且人有一次施展魔法的机会，当遇到怪物时，可以随机走向该怪物房间所连接的边，人从1房间出发，
那么能拿到糖果的期望是多少，1房间总是糖果屋。
我们将糖果屋变成一个个联通块，那么使用魔法的机会肯定是和一号房间的联通块相连的怪物房间，那么我们可以知道 一号房间联通块内的所有糖果必得到，先加上，然后就是对每个相邻怪物房间的相邻联通块中糖果个数求和（一号联通块需要置0），
然后对和÷该房间所连接的边数。
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int maxn = 400005;
5 int ind[maxn];
6 int t;
7 int n,m,k;
8 struct Node
9 {
10 int next,y;
11 } node[maxn];
12 int cnt,head[maxn];
13
14 void add(int x,int y)
15 {
16 node[++cnt].y=y;
17 node[cnt].next=head[x];
18 head[x]=cnt;
19 }
20
21 int moster[maxn],top;
22 bool moster_[maxn];
23 int vis[maxn];
24 int col_num[maxn];
25
26 void dfs(int x,int col,int &cnt)
27 {
28 for(int i=head[x]; i; i=node[i].next)
29 {
30 int y = node[i].y;
31 if(!vis[y] && !moster_[y])
32 {
33 vis[y] = col;
34 dfs(y,col,++cnt);
35 }
36 else if(col == 1 && moster_[y] && !vis[y])
37 {
38 vis[y] = col;
39 moster[++top] = y;
40 }
41 }
42 }
43 int main()
44 {
45 scanf("%d",&t);
46 while(t--)
47 {
48 cnt = top = 0;
49 scanf("%d%d%d",&n,&m,&k);
50 for(int i=1;i<=n;i++)
51 {
52 moster_[i] = vis[i] = col_num[i] = ind[i] = head[i] = 0;
53 }
54 for(int i=1; i<=m; i++)
55 {
56 int u,v;
57 scanf("%d%d",&u,&v);
58 add(u,v);
59 add(v,u);
60 ind[v]++;
61 ind[u]++;
62 }
63 for(int i=1; i<=k; i++)
64 {
65 int x;
66 scanf("%d",&x);
67 moster_[x]=1;
68 }
69 int col = 0;
70 for(int i=1; i<=n; i++)
71 {
72 if(!vis[i] && !moster_[i])
73 {
74 int cnt = 1;
75 vis[i] = ++col;
76 dfs(i,col,cnt);
77 col_num[col] = cnt;
78 }
79 }
80 double init = col_num[1];
81 double ans = 0;
82 col_num[1] = 0;
83 for(int i=1; i<=top; i++)
84 {
85 double tmp = 0;
86 for(int j=head[moster[i]]; j; j=node[j].next)
87 {
88 int y = node[j].y;
89 tmp += col_num[vis[y]];
90 }
91 ans = max(ans,init+tmp/ind[moster[i]]);
92 }
93 printf("%.7f\n",ans);
94 }
95 }
View Code