现在有n个点,给你m条边,每次随机选2个点连边(可能选已经连过的)并且花费1个代价,求使n点联通的期望最小代价。
本题关心每个联通块的规模,但不关心每个联通块具体的点。
然后根据规模记忆化搜索,因为规模无法正常表示成值,所以每次hash一下当前dp的状态,然后记忆化搜索看是否已经算过并返回答案。
对于每个联通块,有两种情况,一种是和另一个联通块相连,第二种是和自己联通块内的点相连接。
设联通块x的规模为ax
对于第二种:每个联通块的连接概率是$(a[x])(a[x]-1)/(n(n+1))对于第一种情况:用两个for两两计算(a[i]a[j])2/(n(n-1))dp(nwe)其中nwe为将a[j]与a[i]相连后的状态
为了精度要求,可以先累加,最后除
由于式子为F=Fp1+Dp2$;所以要先把含F的移到另一边
最后返回答案即可
CODE:
#include <string.h>
#include <stdio.h>
#include <algorithm>
//贴了份题解,自己写了两遍,和题解对拍都没问题,但就是过不了
//欢迎大神指教
#define MAXN 50
#define INF 0x3f3f3f3f
#define MOD 100007
struct sta{
int x[30],flag;
double val;
void clear() {memset(x, 0, sizeof x);}
void sort() {std::sort(x, x + 30);}
int hashme() {
int v = 0;
for (int i = 29, b = 1; i >= 1 && x[i]; i--)
v += x[i] * b, v %= MOD, b *= 30, b %= MOD;
return v;
}
bool operator ==(sta b) {
for (int i = 0; i < 30; i++) if(x[i] != b.x[i]) return false;
return true;
}
bool operator !=(sta b) {
return *this == b ? false: true;
}
}st,hh[MOD];
int n, m, tu, tv;
int p[MAXN], tot[MAXN];
int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}
void inshash(sta st) {
int x = st.hashme();
while (hh[x].flag == 1) {
if (++x == MOD) x = 0;
}
hh[x] = st, hh[x].flag = 1;
}
double gethash(sta st) {
int x = st.hashme();
while (hh[x].flag == 1 && hh[x] != st) {
if (++x == MOD) x = 0;
}
return hh[x] == st ? hh[x].val : -1;
}
double dp(sta ost) {
if(ost.hashme() == n) return 0;
double x = gethash(ost);
if(x != -1.0)return x;
//不会改变连通的方案
double tmp = 0, ans = 0;
for (int i = 0; i < 30; i++)
tmp += (ost.x[i] * (ost.x[i] - 1)) /2;/// 2;
//会把两个非连通子图连通的方案
for (int i = 0; i < 30; i++) {
for (int j = i+1; j < 30; j++) {
if(ost.x[i]==0||ost.x[j]==0)continue;
sta stt = ost;
stt.x[i] += stt.x[j], stt.x[j] = 0;
stt.sort();
ans += ost.x[i] * ost.x[j] * dp(stt);
}
}
ans /= (n * (n-1) / 2), ans++;
ans /= (1 - tmp / (n * (n-1) / 2));
ost.val = ans;
inshash(ost);
return ans;
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < MOD; i++) hh[i].flag = 0;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0; i < m; i++) {
scanf("%d%d", &tu, &tv);
p[find(tu)] = find(tv);
}
st.clear();
int xs = 0;
memset(tot, 0, sizeof tot);
for (int i = 1; i <= n; i++) tot[find(i)]++;
for (int i = 1; i <= n; i++) if(tot[i]) st.x[xs++] = tot[i];
st.sort();
printf("%.10f\n",dp(st));
return 0;
}
/*
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#define mod 1999997
int n,m,fa[70],size[70];
inline int find(int x){
return !fa[x]?x:fa[x]=find(fa[x]);
}
struct state {
double val;
int x[32],flag;
void clear(){
val=flag=0;
memset(x,0,sizeof(x));
}
void sort(){
std::sort(x+1,x+1+n);
}
int hash_get(){
long long sum=0,base=1;
for(int i=n;i&&x[i];--i){
sum+=base*x[i];
base*=30;
base%=mod;sum%=mod;
}
return sum;
}
bool operator != (state m) {
for(int i=n;i;--i){
if(m.x[i]!=x[i]) return 1;
}
return 0;
}
}hsh[mod];
inline double hash_find(state x){
int sum=x.hash_get();
while(hsh[sum].flag&&hsh[sum]!=x){
++sum;
if(sum==mod) sum=0;
}
return hsh[sum]!=x?-1:hsh[sum].val;
}
inline double hash_add(state x){
int sum=x.hash_get();
while(hsh[sum].flag){
++sum;
if(sum==mod) sum=0;
}
hsh[sum]=x;
return hsh[sum].val;
}
inline int merge(int a,int b){
int t1=find(a),t2=find(b);
if(t1==t2) return 0;
fa[t1]=t2;size[t2]+=size[t1];size[t1]=0;
return 0;
}
double dp(state now){
double x=hash_find(now);
if(x!=-1) return x;
if(now.hash_get()==n) return 0;
double self=0,other=0;
for(int i=n;i&&now.x[i];--i){
self+=now.x[i]*(now.x[i]-1)/2;
}
self/=(n*(n-1)/2);
for(int i=n;i&&now.x[i];--i){
for(int j=i-1;j&&now.x[j];--j){
state nwe=now;
nwe.x[i]+=nwe.x[j];nwe.x[j]=0;
nwe.sort();
other+=now.x[i]*now.x[j]*dp(nwe);
}
}
other/=n*(n-1)/2;
other+=1;
other/=1-self;
now.val=other;
hash_add(now);
return other;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) size[i]=1;
for(int i=1;i<=n;++i) hsh[i].clear();
for(int i=1;i<=m;++i){
int x,y;
scanf("%d %d",&x,&y);
merge(x,y);
}
int cnt=0;
state start;start.clear();
for(int i=1;i<=n;++i){
if(size[i]) start.x[++cnt]=size[i];
}
start.sort();
double ans=dp(start);
printf("%.10lf\n",ans);
return 0;
}
*/
0 条评论