TopCoder SRM 561 Orienteering 树形dp

Posted on Edited on In

TopCoder SRM 561 Orienteering 树形dp

题意: 给定了一棵树，以及树上一些节点为关键点，求出随机选出 \(k\) 个关键点后遍历它们的最短路径的期望

遍历关键点相当于要遍历一棵树，考虑遍历一棵树的最优决策

假设我们确定了一个根 \(u\) ，递归考虑每棵子树的问题

发现除了最后留在的那个点对应的路径 \((u,v)\) 以外，所有的边都要被遍历两次

即答案 \(\sum _{e\in E} 2\cdot w(e)-dis(u,v)\)

所以改变根就会发现，答案就是总长*2-直径长度

设总点数为 \(n\) ，包含的总关键点数为 \(m\) ，要选出 \(k\) 个点

Part1 总长计算

考虑对于每一条边计算产生的树跨过它的概率

设这条边两边的关键点的个数分别为 \(a,b(a+b=m)\)

显然，这条边被跨过的概率就是

\(\begin{aligned} 1-\frac{C(a,k)}{C(m,k)}-\frac{C(b,k)}{C(m,k)}\end{aligned}\) (即减去所有选出的关键点都在两边的概率)

设 \(\begin{aligned} f(i)=\frac{C(i,k)}{C(m,k)}=\frac{i!(m-k)!}{m!(i-k)!}\end{aligned}\)

因为这个题目要计算double，所以求阶乘的精度会比较有问题

考虑递推求出 \(f(i)\) ，则有

\(f(i)=\left\{\begin{aligned}1 && i=m \\ \frac{f(i+1)(i+1-k)}{i+1} && i<m\end{aligned}\right.\)

这样递推就能比好得保证精度，然后直接对于每条边计算即可，复杂度为 \(O(n)\)

\[ \ \]

Part2 直径长度计算

直径似乎是一个很难在树形 \(\mathrm{dp}\) 中确定的东西，因此考虑直接先枚举直径的两个端点

定义一棵树的直径两端点为最小的二元组 \((A,B)\) 满足

\(\begin{aligned} A<B，dis(A,B)=\max_{u,v\in V} \{dis(u,v)\}\end{aligned}\)

因为 \(k>1\) ，所以两端点一定不同，不妨设两个端点分别为 \(A,B(A<B)\)

则一个点 \(C\) 可以出现在树上的充要条件是

\((dis(A,C)>dis(A,B) \or dis(A,C)=dis(A,B)\and C \ge B)\)

\(\and (dis(B,C)>dis(A,B) \or dis(B,C)=dis(A,B)\and C \ge A)\)

数出所有可以出现在树上的点个数 \(i\) ，则 \((A,B)\) 为直径的概率应为 \(\frac{C(i-2,k-2)}{C(m,k)}\)

即强制选取了 \((A,B)\) 两个点

依然考虑递推求出

\(\begin{aligned} f(i)=\frac{C(i-2,k-2)}{C(m,k)}=\frac{(i-2)!k(k-1)(m-k)!}{m!(i-k)!}\end{aligned}\)

类似地，得到其递推式为

\(f(i)=\left\{\begin{aligned}\frac{k(k-1)}{m(m-1)} && i=m \\ \frac{f(i+1)(i+1-k)}{i-1} && i<m\end{aligned}\right.\)

这一部分复杂度为 \(O(m^3)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;

typedef pair <int,int> Pii;
typedef long long ll;
typedef double db;
#define mp make_pair
#define pb push_back
#define reg register
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=51;

int n,m,k;
int id[N][N],mk[2510],sz[2510],p[310];
vector <int> G[2520];
db dp[2510],ans;
int dis[2500][2500];

void Dfs(int u,int f) {
	sz[u]=mk[u]>0;
	for(int v:G[u]) if(v!=f) {
		Dfs(v,u),sz[u]+=sz[v];
		ans+=1-dp[sz[v]]-dp[m-sz[v]];
	}
}
void Dfs_Getdis(int rt,int u,int f){
	for(int v:G[u]) if(v!=f) 
		dis[rt][v]=dis[rt][u]+1,Dfs_Getdis(rt,v,u);
}

int A,B;

int Check(int u){
	if(dis[A][u]>dis[A][B]) return 0;
	if(dis[A][u]==dis[A][B] && u<B) return 0;
	if(dis[B][u]>dis[A][B]) return 0;
	if(dis[B][u]==dis[A][B] && u<A) return 0;
	return 1;
}

class Orienteering {
	public:
		double expectedLength(vector <string> field, int K) {
			rep(i,1,n) G[i].clear(); memset(id,0,sizeof id),memset(mk,0,sizeof mk);
			n=m=0,k=K;
			rep(i,0,field.size()-1) rep(j,0,field[i].size()-1) if(field[i][j]!='#') {
				id[i][j]=++n;
				if(field[i][j]=='*') p[mk[n]=++m]=n;
			}
			rep(i,0,field.size()-1) rep(j,0,field[i].size()-1) if(id[i][j]) {
				if(i<iend && id[i+1][j]) G[id[i][j]].pb(id[i+1][j]),G[id[i+1][j]].pb(id[i][j]);
				if(j<jend && id[i][j+1]) G[id[i][j]].pb(id[i][j+1]),G[id[i][j+1]].pb(id[i][j]);
			}
			rep(i,0,m) dp[i]=0;
			dp[m]=1;
			drep(i,m-1,k) dp[i]=dp[i+1]/(i+1)*(i+1-k);
			ans=0,Dfs(1,0),ans*=2; // 期望总长
			// 下面求期望直径长度
			rep(i,1,n) if(mk[i]) Dfs_Getdis(i,i,dis[i][i]=0);
			
			dp[m]=1.0*k*(k-1)/m/(m-1);
			drep(i,m-1,k) dp[i]=dp[i+1]/(i-1)*(i+1-k);
			rep(i,1,m) rep(j,i+1,m) {
				int c=0; A=p[i],B=p[j];
				rep(k,1,m) c+=Check(p[k]);
				if(c>=k) ans-=dis[A][B]*dp[c];
			}
			return ans;
		}
};


\(\begin{aligned} \frac{\begin{aligned} \sum_{i=0}^{min(k,sz[u]) } C(sz[u],i)\cdot C(m-sz[u],k-i)\end{aligned} }{C(m,k)}\end{aligned}\)

\(\begin{aligned} \frac{\begin{aligned} \sum_{i=0}^{min(k,sz[u]) } sz[u]!(m-sz[u])!k!(m-k)!\cdot \end{aligned} }{m!i!(sz[u]-i)!(k-i)!(m-sz[u]-k+i)!}\end{aligned}\)

\(\begin{aligned} 1-\frac{C(sz[u],k)}{C(m,k)}-\frac{C(m-sz[u],k)}{C(m,k)}\end{aligned}\)

\(\frac{C(i,k)}{C(m,k)}=\frac{i!(m-k)!}{m!(i-k)!}\)

i从m for 到 k

f(i)=f(i+1)/i(k-i+1)

\(\frac{C(i-2,k-2)}{C(m,k)}=\frac{(i-2)!k(k-1)(m-k)!}{m!(i-k)!}\)

i=m时， \(f(m)=\frac{k(k-1)}{m(m-1)}\)