250:一个模拟题，我一眼不会做，哈哈
500：给你最多300个点的两棵树，然后tree1的每一个点分别与tree2的每一个点相连，形成一副图，求这副图中长度为K的环的个数的期望。
K <= 7其实说明了这个环是由两条来自不同树的路径构成的！
所以直接暴力求出Count[i]表示长度为i的点对数量就好了。
答案就是Sum ( Count1[i] * Count2[K - 2 - i] * 2 *(n - 2)!) / (n!)
#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <functional>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
using namespace std ;
class TreeUnion
{
public:
double expectedCycles(vector <string> tree1, vector <string> tree2, int K) ;
};
const int N = 310;
int dis1[N][N], dis2[N][N];
void floyd(int d[][N],int n) {
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(d[i][k] && d[k][j]) {
if(!d[i][j]) d[i][j] = d[i][k] + d[k][j];
else d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
}
int Count1[N], Count2[N];
double TreeUnion:: expectedCycles(vector <string> tree1, vector <string> tree2, int K) {
string t1 = "";
for(int i = 0; i < tree1.size(); i++) t1 += tree1[i];
string t2 = "";
for(int i = 0; i < tree2.size(); i++) t2 += tree2[i];
int cnt = 0;
for(int i = 0; i < t1.length(); i++) {
if(t1[i] >= ‘0‘ && t1[i] <= ‘9‘) {
int num = t1[i] - ‘0‘;
int j = i + 1;
while(t1[j] >= ‘0‘ && t1[j] <= ‘9‘) {
num = num * 10 + t1[j] - ‘0‘;
j++;
}
dis1[cnt + 1][num] = dis1[num][cnt + 1] = 1;
cnt ++;
i = j;
}
}
int n = cnt + 1;
cnt = 0;
for(int i = 0; i < t2.length(); i++) {
if(t2[i] >= ‘0‘ && t2[i] <= ‘9‘) {
int num = t2[i] - ‘0‘;
int j = i + 1;
while(t2[j] >= ‘0‘ && t2[j] <= ‘9‘) {
num = num * 10 + t2[j] - ‘0‘;
j++;
}
dis2[cnt + 1][num] = dis2[num][cnt + 1] = 1;
cnt ++;
i = j;
}
}
floyd(dis1, n); floyd(dis2, n);
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
Count1[dis1[i][j]] ++;
Count2[dis2[i][j]] ++;
}
}
double ret = 0;
for(int i = 1; i < K; i++) {
ret += 1.0 * Count1[i] * Count2[K - 2 - i] * 2;
}
return ret / n / (n - 1);
}
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor