题目：
度熊的复仇
Time Limit: 1 Seconds Memory Limit: 65536K
度熊是个喜欢打DOTA的人，有一天他打DOTA的时候被对面的拉比克完全压制，于是他决定选一个自己的拉比克去报仇。
现在，度熊的面前有很多敌人，他可以选择对任意一个敌人施放“弱化能流”。“弱化能流”有连锁反应，连锁的时候伤害不会减弱。如果这个人被击中了那么和他距离在D以内的敌人也会同时被击中，同时会一直这样连锁下去直到条件不满足。每次施放“弱化能流”只会对同一个敌人造成1次伤害，当敌人的血量小于等于0时这个敌人就会死去，但是依然存在，就是说还是可以继续被连锁和向外连锁。
度熊的拉比克有个特性就是有“一击必杀”，当他每次施放“弱化能流”时会有p%的概率触发此特性，那么此次的伤害将会直接变成无穷大，同时其余特性不变，即依然有连锁性而且连锁的伤害依然是无穷大。
现在有N个敌人，每个敌人的血是Ki(1 <= i <= n)，每次“弱化能流”造成的伤害是Att,每次施放需要消耗m的魔法值。
现在度熊想知道：他把所有敌人全部消灭的魔法消耗期望值是多少？
Input
第一行输入一个T代表有T组样例(T <= 20)。
每个样例的第一行输入5个整数n,att,m,p,D，代表有n个敌人，每次“弱化能流”造成的伤害是att，需要消耗m的魔法值，有p%的概率会造成一击必杀，两人的距离在D以内时可以被连锁(1 <= n <= 1000 , 1 <= att <= 100 , 1 <= m <= 10 , 0 <= p <= 100,1 <= D <= 100000)。
接下来n行，每行包含3个整数xi,yi,ki,代表度熊的敌人的位置在(xi,yi)，他的血是ki，度熊的敌人可以认为是一个点(1 <= xi,yi <= 150000, 1 <= ki <= 100)。
Output
对于每个样例，请输出"Case #c : ans".
"c"代表着是第几个样例，样例从1开始；
"ans"代表消灭所有敌人需要消耗的期望魔法值，要求保留两位小数。
Sample Input
2
3 1 1 10 5
0 0 5
1 1 7
2 2 10
4 1 4 13 3
0 0 6
1 1 8
9 9 7
10 10 9
Sample Output
Case #1: 6.51
Case #2: 42.65
特别注意：本题中距离在D以内，意为距离小于D。。。。（导致主号WA的关键句，不过第二天考试RP++了）
首先可以发现，如果很多人连成一片的话，攻击其中任意一个都是等价的。然后就等价于攻击期中K最大的人。
怎么划分集合，我用的是并查集的方法。
然后对每个集合，取出其中最大的K，求出没有“一击必杀”需要多少次才能打死。假设计算出来为x次，那么x次打死的概率为(1.0 - p)^(k-1)
其他的，假设i次打死(i<x)，概率为(10. - p)^(i - 1) * p
乘上次数统计期望。然后各个集合全部相加就好。
代码：
1 #include<cmath> 2 #include<cstdio> 3 using namespace std; 4 typedef long long ll; 5 int T,C,n,a,m,f[1001],k[1001]; 6 ll d; 7 double p,ans; 8 struct poi{ 9 int x,y; 10 void in(){scanf("%d%d",&x,&y);} 11 ll jl(const poi &b)const{ 12 ll i=x-b.x,j=y-b.y; 13 return i*i+j*j; 14 } 15 }s[1001]; 16 int gf(int x){return x!=f[x]?f[x]=gf(f[x]):x;} 17 void lk(int i,int j){ 18 int x=gf(i),y=gf(j); 19 f[x]=y; 20 if(k[x]>k[y])k[y]=k[x]; 21 } 22 double ga(int k){ 23 k=k/a+(k%a?1:0); 24 double a1=0.0,ap=1.0; 25 for(int i=1;i<k;i++){ 26 a1+=i*ap*p; 27 ap*=1.0-p; 28 } 29 return a1+pow(1.0-p,k-1)*k; 30 } 31 int main() 32 { 33 scanf("%d",&T); 34 while(T--){ 35 scanf("%d%d%d%lf%lld",&n,&a,&m,&p,&d); 36 p/=100.0; 37 d*=d; 38 for(int i=0;i<n;i++){ 39 s[i].in(); 40 f[i]=i; 41 scanf("%d",k+i); 42 } 43 for(int i=0;i<n;i++) 44 for(int j=i+1;j<n;j++) 45 if(s[i].jl(s[j])<=d)lk(i,j); 46 ans=0.0; 47 for(int i=0;i<n;i++)if(f[i]==i)ans+=ga(k[i]); 48 printf("Case #%d: %.2lf\n",++C,ans*m); 49 } 50 return 0; 51 }