BZOJ 3143 Luogu P3232 [HNOI2013]游走 (DP、高斯消元)

题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=3143
(luogu) https://www.luogu.org/problemnew/show/P3232

题解: 水题。考虑如何求每个点的期望经过次数: 要求\(1\)号点开始\(n\)号点结束，那么\(1\)号点一定一上来就会经过一次，\(n\)号点一共只会经过\(1\)次。因此对于\(1\)到\(n-1\)的每一个点可以列出一个方程，其中\(1\)号点的方程是\(f[1]=\sum_{edge(u,1),1\le u\le n-1} \frac{f[u]}{du[u]}+1\) (\(du\)为度数), 其余点\(v\)的方程是\(f[v]=\sum_{edge(u,v),1\le u\le n-1} \frac{f[u]}{du[u]}\). 这个方程组有\((n-1)\)个未知数\((n-1)\)个方程，解出来即可。\(n\)号点怎么办？如果列出来其实应该是\(f[n]=\sum_{edge(u,n)} \frac{f[u]}{du[u]}=1\), 但是发现这个方程等价于前\((n-1)\)个方程加起来，所以就不用管了。
我们得到了每个点的期望经过次数，然后就可以轻易得到每条边期望经过次数，对于边\((u,v)\)其期望经过次数为\(\frac{f[u]}{du[u]}+\frac{f[v]}{du[v]}\), 其中\(f[n]\)视为\(0\). 根据期望的线性性，总得分期望就等于每条边期望经过次数乘以边权再求和，所以根据排序不等式给期望次数越小的边安排越大的边权即可。

时间复杂度\(O(n^3+m\log m)\).

代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;

inline int read()
{
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    if(f) return x;
    return -x;
}

const int N = 500;
namespace Gauss
{
    double a[N+3][N+3],b[N+3],sol[N+3];
    void gauss(int n)
    {
        for(int i=1; i<=n; i++)
        {
            if(a[i][i]==0)
            {
                bool found = false;
                for(int j=i+1; j<=n; j++)
                {
                    if(a[i][j]!=0)
                    {
                        for(int k=i; k<=n; k++) swap(a[i][k],a[j][k]);
                        swap(b[j],b[i]);
                        found = true; break;
                    }
                }
                if(!found) continue;
            }
            for(int j=i+1; j<=n; j++)
            {
                if(a[j][i]!=0)
                {
                    double coe = -a[j][i]/a[i][i];
                    for(int k=i; k<=n; k++) {a[j][k] += coe*a[i][k];}
                    b[j] += coe*b[i];
                }
            }
        }
        for(int i=n; i>=1; i--)
        {
            for(int j=i+1; j<=n; j++)
            {
                b[i] -= a[i][j]*sol[j];
            }
            sol[i] = b[i]/a[i][i];
        }
    }
}
struct AEdge
{
    int u,v;
} e[N*N+3];
int du[N+3];
double f[N+3];
double coe[N*N+3];
int permu[N*N+3];
int n,m,en;

bool cmp(int x,int y) {return coe[x]>coe[y];}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&e[i].u,&e[i].v);
        du[e[i].u]++; du[e[i].v]++;
    }
    for(int i=1; i<n; i++) Gauss::a[i][i] = -1.0;
    for(int i=1; i<=m; i++)
    {
        int u = e[i].u,v = e[i].v;
        if(u==n || v==n) continue;
        Gauss::a[u][v] += 1.0/du[v]; Gauss::a[v][u] += 1.0/du[u];
    }
    Gauss::b[1] = -1.0;
    Gauss::gauss(n-1);
    for(int i=1; i<n; i++) f[i] = Gauss::sol[i];
    for(int i=1; i<=m; i++)
    {
        int u = e[i].u,v = e[i].v;
        coe[i] = f[u]/du[u]+f[v]/du[v];
    }
    for(int i=1; i<=m; i++) permu[i] = i;
    sort(permu+1,permu+m+1,cmp);
    double ans = 0.0;
    for(int i=1; i<=m; i++) {ans += coe[permu[i]]*i;}
    printf("%.3lf\n",ans);
    return 0;
}

BZOJ 3143 Luogu P3232 [HNOI2013]游走 (DP、高斯消元)

原文：https://www.cnblogs.com/suncongbo/p/11150395.html