这的确是一道树形\(dp\)的好(毒瘤)题,理一理思路应该也不是太难,主要是基环树那\(50\)分不好拿
Solution [NOI2012]迷失游乐园
题目大意:给定一个\(n\)个点\(m\)条边的无向图,每条边有一长度,问等概率选一点出发,等概率走到与当前节点相邻节点,不重复走一节点,所走路径的期望长度
分析:我们首先来看\(50\)分,也就是原图是一颗树的情况.
先假设以\(1\)号点为根,那么设\(f[u]\)为从\(u\)出发,在这个子树内走,所走路径的期望长度.
显然我们\(1\;min\)就可以列出来一个状态转移方程:
\[f[u] = \frac{\sum{(f[v] + w_{u,v})}}{siz[u]}\]
其中\(v\)为\(u\)的儿子,\(w_{u,v}\)为连接\(u,v\)两点的路径长度,\(siz[u]\)为\(u\)点的儿子个数
这个正确性是显而易见的,路径长度乘上概率而已
设\(ans[u]\)为从\(u\)点出发,所走路径的期望长度,也就是以\(u\)点为根,在这颗树内所走路径的期望长度,最终答案为\(ans = \frac{\sum_{1}^{n}{ans_{i}}}{n}\)
\(ans[1] = f[1]\),但是我们如何通过\(ans[1]\)来求其它的\(ans\)?处理技巧有很多,比如记录一个父亲,但是如果一个点连着很多点就可以轻松把你卡掉,那么我们可以用一种类似\(bfs\)的方法来求\(ans\)
比如这颗树:
我们已经知道了以\(1\)为根的答案,也就是\(ans[1]\),假设现在我们要求\(ans[2]\),实际上就是以\(2\)为根的答案.这个树变成了酱紫:
画图真的逼死强迫症
我们会很愉快的发现,\(3,6\)这一颗子树的\(f\)值并没有什么变动诶,\(4,5\)也是酱紫的,那么这意味这什么?我们可以在\(O(1)\)的时间内从已知的\(ans\)值推出与它相邻节点的\(ans\)值,那么只需要一次\(bfs\)就可以在\(O(n)\)的时间内算出所有的\(ans\)值啦!
设我们已知\(ans[u]\),要推出\(ans[v]\)(\(v\)是\(u\)的相邻节点)
那么设少了\(v\)这个点后,\(ans[u]\)变为了\(tmp\),那么:
\(tmp = \frac{ans[u] \times degree[u] - w_{u,v} - f[v]}{degree[u] - 1}\)
其中\(degree[u]\)表示\(u\)点度数,当\(degree[u] = 1\)时特判\(tmp = 0\)(因为\(siz\)是以\(1\)为根是算的,不能直接用)
然后我们可以算\(ans[v]\)啦
\(ans[v] = \frac{f[v] * siz[v] + w_{u,v} + tmp}{siz[v] + 1}\),原来\(v\)一直作为子树存在,所以可以放心的用\(siz[v]\)
然后\(50 pts\) get!
然后就是毒瘤的基环树了……
我们来看看有基环时图长啥样子
好像有点歪,不管了就酱紫了
我们发现所谓基环树就是一个大的环上"生长"出了很多棵树
我们一个拓扑排序就可以把环给逮出来,基本操作
我们定义"上"这个方向是从树往基环走,"下"是从基环往树上走,每棵树的树根都在基环上
那么基环的存在对"下"的答案是没有影响的,我们只需要将"上"这部分的答案累计入答案即可
在基环上我们有两个行走防线,顺时针和逆时针,那么对于一颗树,我们可以在根新建两个虚拟点,分别表示在基环上的两个行走方向,虚拟点的\(f\)值即为在基环上路径的期望长度,当然,在程序实现中我们并不需要真的建点,只需要改改\(ans\)就好了,然后套用第一问的方法,用树根的\(ans\)去向"下"更新子树内\(ans\)即可,最后答案任为\(\frac{\sum_{1}^{n}ans_{i}}{n}\)
以顺时针走举例吧,逆时针差不多,我们设\(tot\)为从\(i\)这个点第一步向"上"走,顺时针走的期望长度:
\[tot = \sum[P_j \cdot (f[j] \cdot \frac{siz[j]}{siz[j] + 1} + w_{j-1,j})]\]从\(j\)这个点向下走的期望长度为\(f[j]\),走进去的概率为\(\frac{siz[j]}{siz[j] + 1}\),注意:如果下一个点为起始点,分母为\(siz[j]\)(因为不能访问重复点,也就必须走进子树内)
对于\(P_j\),每次离开循环时我们将其乘上\(\frac{1}{siz[j] + 1}\),因为不向下走进子树,继续在环上走的概率是\(\frac{1}{siz[j] + 1}\)
虽然我们有两个虚拟点,但是我们可以将顺逆时针的答案累计起来再去更新\(ans\).那么我们现在设\(sum\)为顺逆时针的\(tot\)之和
\[ans[u] = \frac{f[u] * siz[u] + sum}{siz[u] + 2}\]
然后愉快的更新一波\(ans\)即可
上丑陋的代码:注意特判0!!
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef double type;
const int maxn = 1e5 + 100;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
return x;
}
struct Edge{int to,dist;};
vector<Edge> G[maxn];int degree[maxn];
inline void addedge(int from,int to,int dist){
G[from].push_back(Edge{to,dist});
degree[to]++;
}
int n,m;
namespace Tree{//为一棵树时
type f[maxn],ans[maxn];
int vis[maxn],siz[maxn];
void dfs(int u,int faz){//树形dp求f
for(auto e : G[u]){
if(e.to == faz)continue;
siz[u]++;
dfs(e.to,u);
f[u] += f[e.to] + e.dist;
}
if(siz[u])f[u] /= siz[u];//特判siz是否为0
}
void bfs(int s){//更新答案
queue<int> Q;
Q.push(s),vis[s] = 1;
while(!Q.empty()){
int u = Q.front();Q.pop();
for(auto e : G[u]){
if(vis[e.to])continue;
int nsiz = siz[u] + (u != s);//nsiz即度数,除了起始点(根节点)都要加1
type newfu = (nsiz == 1) ? 0 : (ans[u] * nsiz - e.dist - f[e.to]) / (nsiz - 1);
ans[e.to] = (f[e.to] * siz[e.to] + newfu + e.dist) / (siz[e.to] + 1);//这两处见上文
Q.push(e.to),vis[e.to] = 1;
}
}
}
inline void work(){
dfs(1,0);
ans[1] = f[1];
bfs(1);
type tmp = 0;
for(int i = 1;i <= n;i++)
tmp += ans[i];
printf("%.5f\n",tmp / n);
}
}
namespace Circle{
type f[maxn],ans[maxn];
int vis[maxn],siz[maxn],inc[maxn],nxt[maxn],pre[maxn],tag[maxn],dis[32][32],ctot;//tag[u]表示节点u对应环上点的编号(离散化),inc表示是否在环上,dis表示距离
void toposort(){//拓扑找环
queue<int> Q;
for(int i = 1;i <= n;i++)inc[i] = 1;
for(int i = 1;i <= n;i++)
if(degree[i] == 1)Q.push(i);
while(!Q.empty()){
int u = Q.front();Q.pop();
inc[u] = 0;
for(auto e : G[u])
if(--degree[e.to] == 1)Q.push(e.to);
}
}
void dfs(int u,int faz){//树形dp
for(auto e : G[u]){
if(e.to == faz || inc[e.to])continue;
siz[u]++;
dfs(e.to,u);
f[u] += f[e.to] + e.dist;
}
if(siz[u])f[u] /= siz[u];
}
void bfs(int s){//同上
queue<int> Q;
Q.push(s),vis[s] = 1;
while(!Q.empty()){
int u = Q.front();Q.pop();
for(auto e : G[u]){
if(vis[e.to] || inc[e.to])continue;//这里注意,bfs是别跑环上去了,就在子树内更新
int nsiz = siz[u] + (u != s);
type newfu = (nsiz == 1) ? 0 : (ans[u] * nsiz - e.dist - f[e.to]) / (nsiz - 1);
ans[e.to] = (f[e.to] * siz[e.to] + newfu + e.dist) / (siz[e.to] + 1);
Q.push(e.to),vis[e.to] = 1;
}
}
}
vector<int> cir;
void dfs_circle(int u,int faz){//找出环上对应关系
if(tag[u])return;
tag[u] = ++ctot;
for(auto e : G[u]){
if(!inc[e.to] || e.to == faz)continue;
pre[e.to] = u,nxt[u] = e.to;
dfs_circle(e.to,u);
dis[tag[u]][tag[e.to]] = dis[tag[e.to]][tag[u]] = e.dist;
break;
}
}
inline void work(){
toposort();//找环
for(int i = 1;i <= n;i++)
if(inc[i])dfs(i,0),cir.push_back(i);//从环上向"下"求出f
dfs_circle(cir[0],0);
for(int now : cir){//枚举环上点
type div = 1.0,tot = 0,w = 0;
for(int pos = nxt[now];pos != now;pos = nxt[pos]){
w = dis[tag[pre[pos]]][tag[pos]];
if(nxt[pos] == now)tot += div * (w + f[pos]);
else tot += div * (w + f[pos] * siz[pos] / (siz[pos] + 1));
div /= (siz[pos] + 1);
}
div = 1.0,w = 0;
for(int pos = pre[now];pos != now;pos = pre[pos]){
w = dis[tag[pos]][tag[nxt[pos]]];
if(pre[pos] == now)tot += div * (w + f[pos]);
else tot += div * (w + f[pos] * siz[pos] / (siz[pos] + 1));
div /= (siz[pos] + 1);
}
ans[now] = (f[now] * siz[now] + tot) / (siz[now] + 2);//加入了2个虚拟点
}//同上文题解
for(int now : cir)siz[now] += 2;//虽然程序没有加入虚拟点,对siz的影响任然要加入,上文siz不加是因为我们要算概率
for(int now : cir)bfs(now);//更新答案
type sum = 0;
for(int i = 1;i <= n;i++)sum += Circle::ans[i];
printf("%.5f\n",sum / n);
}
}
int main(){
n = read();m = read();
for(int u,v,d,i = 1;i <= m;i++)
u = read(),v = read(),d = read(),addedge(u,v,d),addedge(v,u,d);
if(m == n - 1)Tree::work();
else Circle::work();
return 0;
}
%f和%lf真的迷,下次我浮点数用\(cin / cout\)来\(IO\)算了,坑了我很多次了,Windows下迷得很
祝大家都可以愉快的A了这道题