Description
傲娇少女幽香是一个很萌很萌的妹子, 而且她非常非常地有爱心, 很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们. 这不, 幻想乡突然发生了地震, 所有的道路都崩塌了. 现在的首要任务是尽快让幻想乡的交通体系重新建立起来. 幻想乡一共有 \(n\) 个地方, 那么 最快的方法当然是修复 \(n-1\) 条道路将这 \(n\) 个地方都连接起来. 幻想乡这 \(n\) 个地方本来是连通的, 一共有 \(m\) 条边. 现在这 \(m\) 条边由于地震的关系, 全部都毁坏掉了. 每条边都有一个修复它需要花费的时间, 第 i 条边所需要的时间为 \(e_i\). 地震发生以后, 由于幽香是一位 人生经验丰富, 见得多了的长者, 她根据以前的经验, 知道每次 地震以后, 每个 \(e_i\) 会是一个 \(0\) 到 \(1\) 之间均匀分布的随机实数. 并且所有 \(e_i\) 都是完全独立的. 现在幽香要出发去帮忙修复道路了, 她可以使用一个神奇的大魔法, 能够 选择需要的那 \(n-1\) 条边, 同时开始修复, 那么修复完成的时间就是这 \(n-1\) 条边的 \(e_i\) 的最大值. 当然幽香会先使用一个更加神奇的大魔法来观察出每条边 \(e_i\) 的值, 然后再选择完成时间最小的方案. 幽香在走之前, 她想知道修复完成的时间的期望是多少呢?
Input
第一行两个数 \(n, m\), 表示地方的数量和边的数量. 其中点从 \(1\) 到 \(n\) 标号.
接下来 \(m\) 行, 每行两个数 \(a, b\), 表示点 \(a\) 和点 \(b\) 之间原来有一条边.
这个图不会有重边和自环.
Output
一行输出答案, 四舍五入保留 6 位小数.
Sample Input
5 4
1 2
1 5
4 3
5 3Sample Output
0.800000Hint
以下内容与题意无关, 对于解题也不是必要的.
对于 \(n\) 个 \([0, 1]\) 之间的随机变量 \(x_1, x_2, ..., x_n\), 第 \(k\) 小的那个的期望值是 \(\frac{k}{n+1}\).
Sample Explanation
对于第一个样例, 由于只有 4 条边, 幽香显然只能选择这 4 条, 那么答案就是 4 条边的 \(e_i\) 中最大的数的期望, 由提示中的内容, 可知答案为 0. 8.
Data Range
对于所有数据:\(n \leq 10, m \leq \frac{n \cdot (n - 1)}{2}, n, m \geq 1\).
对于 15% 的数据:\(n \leq 3\).
另有 15% 的数据:\(n \leq 10, m = n\).
另有 10% 的数据:\(n \leq 10, m = \frac{n \cdot (n - 1)}{2}\).
另有 20% 的数据:\(n \leq 5\).
另有 20% 的数据:\(n \leq 8\).
Solution
参见网上各大神做法:
首先这里有一种比较好像的做法, 也是 @Burst_Zero 告诉我的做法, 就是说各种期望用微积分推一下然后瞎搞出来就能出结果的做法. 但是我大概试了一下, 发现精度会被卡差不多 \(5 \times 10^{-7}\) 这个位置,long double 都无法胜任...... 所以为了偷懒不写高精我们 就挖出了这样一个好东西:__float128 (可能有的老旧机器不兹磁, 这样的话就只能手写高位高精了 TAT)
下面是转发 @PoPoQQQ 的题解:http://blog.csdn.net/popoqqq/article/details/44858691
首先既然权值在 \([0,1]\) 之间均匀分布那么两条边权值相同的概率为 0 于是我们只考虑所有边边权都不同的情况
如果最小生成树上的最大边为 \(x\), 那么权值小于 \(x\) 的边一定不能将这个图连通, 而权值 \(\leq x\) 的边就可以
因此对于一个 \(x\), 如果我们求出【只有边权小于 \(x\) 的边存在时这个图不连通】的概率, 那么这个概率就是答案 \(\geq x\) 的概率
不妨设这个概率为 \(f(x)\) 那么这个 \(f(x)\) 其实是关于 x 的一个多项式 而答案就是:
\[\int_0^1 f(x) \cdot dx\]
至于为什么答案是 \(f(x)\) 的积分可以感性理解下...... 我数死早......
下面就是如何求 \(f(x)\) 了
首先【边权小于 \(x\) 的概率】就是 \(x\), 因此这个问题等价于【每条边有 \(x\) 的概率出现时这个图不连通的概率】
然后就是经典做法了......
clj 只说到这...... 然后我扒了半天代码才反应过来怎么做 QAQ 我好弱 QAQ
这个做法和 POJ1737 连通图的做法是类似的
首先我们考虑补集法求这个图连通的概率 然后用 1 减掉就行了
然后我们枚举每一个诱导子图计算这个子图连通的概率
首先我们任选子图中的一点 \(p\), 然后枚举哪些点与 \(p\) 相连
设 \(p\) 所在联通块联通的概率为 \(q\),\(x\) 所在联通块与其它点之间共有 \(k\) 条边, 那么 这种情况不连通的概率就是 \(q \cdot (1-x)^k\)
从 1 中减掉所有不连通的概率就是这个状态连通的概率了......
以上是大神题解
话说后面一半内容倒是想出来了, 然而前面的数学推理我比较弱, 所以没有想出来 QAQ
另外还有一个神犇似乎没有用上高精直接求出情况数最后再除, 因为我没有这样做 (至少当前 没有这样做), 所以就不把题解粘过来了, 直接上链接:http://blog.csdn.net/skywalkert/article/details/47792065
Source Code
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long lli;
// typedef long double llf;
typedef __float128 llf;
const int maxn = 15, maxm = 100, maxn_pw = 1100;
int lowest_digit(int x) { return x & -x; }
int get_digits(int x) { int res = 0;
for (; x; x -= lowest_digit(x)) res++;
return res; }
class Polynomial { public:
vector<lli> vec;
int size() { return vec.size(); }
lli& operator [] (int x) { return vec[x]; }
Polynomial(int sz) { vec = vector<lli>(sz, 0); }
Polynomial(void) { vec = vector<lli>(1, 0); }
};
Polynomial operator + (Polynomial a, Polynomial b)
{
Polynomial c(max(a.size(), b.size()));
for (int i = 0; i < a.size(); i++)
c[i] += a[i];
for (int i = 0; i < b.size(); i++)
c[i] += b[i];
return c;
}
Polynomial operator - (Polynomial a, Polynomial b)
{
Polynomial c(max(a.size(), b.size()));
for (int i = 0; i < a.size(); i++)
c[i] += a[i];
for (int i = 0; i < b.size(); i++)
c[i] -= b[i];
return c;
}
Polynomial operator * (Polynomial a, Polynomial b)
{
Polynomial c(a.size() + b.size() - 1);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
c[i + j] += a[i] * b[j];
return c;
}
llf integrate(Polynomial a)
{
llf res = 0.0;
for (int i = 0; i < a.size(); i++)
res += (llf)a[i] / (i + 1);
return res;
}
ostream& operator << (ostream& out, Polynomial a)
{
for (int i = a.size() - 1; i > 0; i--)
out << a[i] << "*x^" << i << " + ";
out << a[0];
return out;
}
int n, m, n_pow;
int edges[maxn];
Polynomial pow_prec[maxm]; // pow[i] = (1-x)^i
Polynomial dp[maxn_pw];
int main(int argc, char** argv)
{
scanf("%d%d", &n, &m);
n_pow = 1 << n;
// A fancy way of constructing a graph...
for (int i = 1, a, b; i <= m; i++) {
scanf("%d%d", &a, &b);
edges[a] |= 1 << (b - 1);
edges[b] |= 1 << (a - 1);
}
// Preprocessing powers: (1 - x) ^ i
pow_prec[0] = Polynomial(1);
pow_prec[1] = Polynomial(2);
pow_prec[0][0] = 1; // pow[0] = 1
pow_prec[1][0] = 1; pow_prec[1][1] = -1; // pow[1] = 1-x
for (int i = 2; i <= m; i++)
pow_prec[i] = pow_prec[i - 1] * pow_prec[1];
// Processing graph connectivity, compressed with binary.
for (int i = 1; i < n_pow; i++) {
dp[i] = Polynomial(1);
dp[i][0] = 1;
int x; // x is the lowest available digit in i, always gurantted an existent x.
for (x = 1; x <= n; x++)
if ((i >> (x - 1)) & 1)
break;
// Possibly taken digits off...
for (int j = i ^ (1<<(x-1)); j; (--j) &= i ^ (1<<(x-1))) {
int tmp = i ^ j, cnt = 0;
// Iterate all accessible points and check.
for (int k = 1; k <= n; k++)
if ((tmp>>(k-1)) & 1)
cnt += get_digits(edges[k] & j);
// "dynamic programming"
dp[i] = dp[i] - dp[tmp] * pow_prec[cnt];
}
}
// Evaluating integration
Polynomial res_poly = pow_prec[0] - dp[n_pow - 1];
// cout << res_poly << endl;
llf res = integrate(res_poly);
cout << fixed << setprecision(6) << (double)res << endl;
return 0;
}