首先想到怎么求出每一条边 \(i\) 在每次游走中被经过次数的期望 \(f_i\),那么答案就可以贪心地取。(即让最大的 \(f_i\) 权值设为 \(1\),次大的设为 \(2\),……,最小的设为 \(m\))
但是发现不好统计,或者时间无法承受。
发现点数很小(\(n\leq 500\)),于是想到怎么通过点的期望值转移到边上。
容易得到:如果设每一个点 \(u\) 在每次游走中被经过次数的期望 \(g_u\),每个点的度数为 \(deg_u\),然后假设某一条边 \(i\) 为 \((u,v)\),那么有 \(f_i=\dfrac{g_u}{deg_u}+\dfrac{g_v}{deg_v}\)。
所以我们只需要求出 \(g\) 就可以得到 \(f\) 了。
容易得到状态转移方程:
\[g_u= \begin{cases} 1+\sum\limits_{(u,v)}\dfrac{g_v}{deg_v}&u=1\\ \sum\limits_{(u,v)}\dfrac{g_v}{deg_v}&1<u<n\\ \end{cases} \]
解释一下:
首先为什么 \(u=1\) 的时候要比其他时候多加 \(1\),因为初始化的时候本来就应该是 \(g_1=1\)。
然后为什么 \(g_n\) 不考虑,因为到了 \(n\) 之后就结束游走了,不可能再走向下一条边。
然后这个状态转移方程就可以看成是有 \(n-1\) 个未知数,\(n-1\) 条式子的方程,用高斯消元做就好了。
最后代码如下:
#include<bits/stdc++.h>
#define N 510
#define M 125010
using namespace std;
int n,m;
int deg[N],from[M],to[M];
double a[N][N],x[N],f[M];
vector<int>e[N];
void Gauss()
{
for(int i=1;i<n;i++)
{
int p=i;
for(int j=i+1;j<n;j++)
if(fabs(a[j][i])>fabs(a[p][i])) p=j;
if(i!=p) swap(a[i],a[p]);
for(int j=i+1;j<n;j++)
{
double tmp=a[j][i]/a[i][i];
for(int k=i;k<=n;k++) a[j][k]-=a[i][k]*tmp;
}
}
for(int i=n-1;i>=1;i--)
{
for(int j=i+1;j<n;j++) a[i][n]-=x[j]*a[i][j];
x[i]=a[i][n]/a[i][i];
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&from[i],&to[i]);
e[from[i]].push_back(to[i]);
e[to[i]].push_back(from[i]);
deg[from[i]]++,deg[to[i]]++;
}
for(int u=1;u<n;u++)
{
a[u][u]=1;
for(int i=0,size=e[u].size();i<size;i++)
{
int v=e[u][i];
if(v!=n) a[u][v]-=1.0/deg[v];
}
}
a[1][n]=1;
Gauss();
for(int i=1;i<=m;i++)
{
int u=from[i],v=to[i];
if(u!=n) f[i]+=x[u]/deg[u];
if(v!=n) f[i]+=x[v]/deg[v];
}
sort(f+1,f+m+1);
double ans=0;
for(int i=1;i<=m;i++)
ans+=i*f[m-i+1];
printf("%.3lf\n",ans);
return 0;
}
原文地址:http://www.cnblogs.com/ez-lcw/p/16837272.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性