[BZOJ3143/Luogu3232][HNOI2013]游走(高斯消元,贪心)

发布于 2018-05-24  71 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3143/Luogu3232][HNOI2013]游走(高斯消元,贪心)

Description

一个无向连通图,顶点从1编号到N,边从1编号到M。
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

Tag

高斯消元,贪心

解决思路

如果我们能够知道每一条边期望经过的次数,那么根据期望的累加性,就按照期望从大到小排序,贪心地分配编号。
又因为我们知道经过一条边的期望次数等于经过它的两个端点的期望次数分别除以点度数再累加,即对于边$$u-v$$来说$$w=\frac{W[u]}{Degree[u]}+\frac{W[v]}{Degree[v]}$$,问题转化为求经过每一个点的期望次数。
设经过点$$u$$的期望次数为$$F[u]$$,则对于$$u$$的出边$$u-v$$,有
\[F[u]=\sum \frac{F[v]}{Degree[v]}\]
由于是从$$1$$出发的,所以$$F[1]=\sum \frac{F[v]}{Degree[v]}+1$$
由于到达$$n$$后不再行动,所以$$F[n]=0$$
可以列出$$n$$个方程,大力高斯消元就好。

代码

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

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=510;
const int maxM=maxN*maxN;
const ld eps=1e-7;
const int inf=2147483647;

int n,m;
ld Degree[maxN];
int U[maxM],V[maxM];
ld Mat[maxN][maxN],W[maxM];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&U[i],&V[i]);
        Degree[U[i]]+=1.0;Degree[V[i]]+=1.0;
    }
    for (int i=1;i<=m;i++)
    {
        Mat[U[i]][V[i]]-=(ld)1.0/Degree[V[i]];
        Mat[V[i]][U[i]]-=(ld)1.0/Degree[U[i]];
    }
    for (int i=1;i<=n+1;i++) Mat[n][i]=0;
    for (int i=1;i<=n;i++) Mat[i][i]=1;
    Mat[1][n+1]=1;

    for (int i=1;i<=n;i++)
    {
        int j=i;
        while (fabs(Mat[j][i])<eps) j++;
        for (int k=1;k<=n+1;k++) swap(Mat[j][k],Mat[i][k]);
        ld d=(ld)1.0/Mat[i][i];
        for (int k=1;k<=n+1;k++) Mat[i][k]*=d;
        for (int k=1;k<=n;k++)
            if ((i!=k)&&(fabs(Mat[k][i])>eps))
            {
                d=Mat[k][i]/Mat[i][i];
                for (int l=1;l<=n+1;l++) Mat[k][l]=Mat[k][l]-Mat[i][l]*d;
            }
    }
    for (int i=1;i<=m;i++) W[i]=Mat[U[i]][n+1]/Degree[U[i]]+Mat[V[i]][n+1]/Degree[V[i]];
    sort(&W[1],&W[m+1]);
    ld Ans=0;
    for (int i=1;i<=m;i++) Ans=Ans+W[i]*(ld)(m-i+1);
    printf("%.3LF\n",Ans);
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3143/Luogu3232][HNOI2013]游走(高斯消元,贪心)


HNCJ OIer 一枚