【BZOJ3143】游走（HNOI2013）-DP+概率期望+高斯消元

测试地址：游走
做法：本题需要用到DP+概率期望+高斯消元。
首先根据期望可加性，我们知道路径和的期望等于每条边的期望经过次数乘上边权。又根据排序不等式，我们知道给大的期望次数分配小的编号是最优的，那么现在问题就变成求每条边的期望经过次数。
我们可以先求出每个点的期望经过次数pi$p_i$，然后边(i,j)$(i,j)$的期望经过次数就是pideg(i)+pjdeg(j)$\frac{p_i}{deg(i)}+\frac{p_j}{deg(j)}$，其中deg(i)$deg(i)$表示点i$i$的度数。那么对于每个点我们有状态转移方程：
pi=∑(i,j)∈E1deg(j)pj$p_i=\sum _{(i,j)\in E}\frac{1}{deg(j)}{p}_j$
把所有点的方程列出来后，O(n3)$O(n^3)$高斯消元直接把未知数求出来即可。
这里要注意几个问题：一是因为点n$n$是终止节点，所以它对所有其他点都不会做出贡献，直接去掉。二是点1$1$的方程实际上是p1=1+∑(1,j)∈E1deg(j)pj$p_1=1+\sum _{(1,j)\in E}\frac{1}{deg(j)}{p}_j$，因为游走是从点1$1$开始的，所以必定先有一次经过，然后才开始随机游走的过程。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
int n,m;
double g[510][510]={0},deg[510]={0},p[510];
struct edge
{
    int a,b;
    double p;
}e[300010];

void gauss(int n)
{
    for(int i=1;i<=n;i++)
    {
        int mx=i;
        for(int j=i;j<=n;j++)
            if (fabs(g[j][i])>fabs(g[mx][i])) mx=j;
        for(int j=i;j<=n+1;j++)
            swap(g[i][j],g[mx][j]);
        for(int j=1;j<=n;j++)
            if (j!=i)
            {
                for(int k=i+1;k<=n+1;k++)
                    g[j][k]-=g[j][i]*g[i][k]/g[i][i];
                g[j][i]=0.0;
            }
    }
}

bool cmp(edge a,edge b)
{
    return a.p>b.p;
}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&e[i].a,&e[i].b);
        deg[e[i].a]++,deg[e[i].b]++;
    }
    for(int i=1;i<=m;i++)
    {
        if (e[i].b!=n) g[e[i].a][e[i].b]=-1.0/deg[e[i].b];
        if (e[i].a!=n) g[e[i].b][e[i].a]=-1.0/deg[e[i].a];
    }
    for(int i=1;i<n;i++)
        g[i][i]=1.0;
    g[1][n]=1.0; 
}

void work()
{
    gauss(n-1);
    for(int i=1;i<n;i++)
        p[i]=g[i][n]/g[i][i];
    for(int i=1;i<=m;i++)
    {
        e[i].p=0;
        if (e[i].a!=n) e[i].p+=p[e[i].a]/deg[e[i].a];
        if (e[i].b!=n) e[i].p+=p[e[i].b]/deg[e[i].b];
    }
    sort(e+1,e+m+1,cmp);
    double ans=0.0;
    for(int i=1;i<=m;i++)
        ans+=e[i].p*(long double)i;
    printf("%.3lf",ans);
}

int main()
{
    init();
    work();

    return 0;
}