做网站和谷歌推广一共多少钱,广东网站建设效果,莱芜的招聘平台,成品短视频app下载有哪些破解版图上游走
金牌导航 期望-6
题目大意
给出一个无向连通图#xff0c;小明初始在点1#xff0c;每一步等概率地走向相连的其他点#xff0c;当走到n时结束#xff0c;定义分数从1为走到n的过程中经过的边的编号之和#xff0c;现在让你给这m条边重新编号#xff0c;使最…图上游走
金牌导航 期望-6
题目大意
给出一个无向连通图小明初始在点1每一步等概率地走向相连的其他点当走到n时结束定义分数从1为走到n的过程中经过的边的编号之和现在让你给这m条边重新编号使最大期望分数最小
输入样例
3 3
2 3
1 2
1 3输出样例
3.333解题思路
一条边的贡献期望经过次数×\times×编号 为了使期望分数最小让期望经过次数大的编号小即可 那么如何求边的期望经过次数呢 对于连接x,y的边有 slisxdegxsydegysl_i\frac{s_x}{deg_x}\frac{s_y}{deg_y}slidegxsxdegysy 其中sls分别为边点的期望次数deg为连接的边数 意思就是从x的点有1degx\frac{1}{deg_x}degx1的概率走过这条边再乘上sxs_xsx即为从x点走过该边的概率y同理 求sl的方法已经有了那么考虑求s 对于s我们有式子 sis1deg1s2deg2...sdegidegdegis_i\frac{s_1}{deg_1}\frac{s_2}{deg_2}...\frac{s_{deg_i}}{deg_{deg_i}}sideg1s1deg2s2...degdegisdegi 里面的数表示和i相连的数 移项得到 0−sis1deg1s2deg2...sdegidegdegi0-s_i\frac{s_1}{deg_1}\frac{s_2}{deg_2}...\frac{s_{deg_i}}{deg_{deg_i}}0−sideg1s1deg2s2...degdegisdegi 这样我们就得到n-1个式子到n后不会再往回走所以关于n的式子不要 注对于1的式子有初始的一次移项后得到的是 −1−sis1deg1s2deg2...sdegidegdegi-1-s_i\frac{s_1}{deg_1}\frac{s_2}{deg_2}...\frac{s_{deg_i}}{deg_{deg_i}}−1−sideg1s1deg2s2...degdegisdegi 对于这n-1个式子我们高斯消元得到s然后求结果即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 510
using namespace std;
int n, m, x, y, tot, maxn, head[N];
double ans, l[2*N*N], deg[N], f[N][N];
struct rec
{int to, next;
}a[2*N*N];
double abss(double x)
{if (x 0) return -x;return x;
}
void add(int x, int y)
{a[tot].to y;a[tot].next head[x];head[x] tot;a[tot].to x;a[tot].next head[y];head[y] tot;deg[x] 1.0;deg[y] 1.0;
}
void gaus(int n)//高斯消元
{for (int i 1; i n; i){maxn i;for (int j i 1; j n; j)if (abss(f[j][i]) abss(f[maxn][i]))maxn j;for (int j 1; j n 1; j)swap(f[i][j], f[maxn][j]);for (int j 1; j n; j)if (i ! j)for (int k i 1; k n 1; k)f[j][k] - f[i][k] * (f[j][i] / f[i][i]);}for (int i 1; i n; i)f[i][n 1] / f[i][i];return;
}
int main()
{scanf(%d%d, n, m);for (int i 1; i m; i){scanf(%d%d, x, y);add(x, y);}for (int i 1; i n; i){f[i][i] -1.0;for (int j head[i]; j; j a[j].next)if (a[j].to ! n)//到n后不走了f[i][a[j].to] 1.0 / deg[a[j].to];//得出方程}f[1][n] -1.0;gaus(n - 1);for (int i 1; i m; i)l[i] f[a[i*2].to][n] / deg[a[i*2].to] f[a[i*2-1].to][n] / deg[a[i*2-1].to];//求出期望sort(l 1, l 1 m);reverse(l 1, l 1 m);//从大到小for (int i 1; i m; i)ans l[i] * i;printf(%.3lf, ans);return 0;
}
