喜欢的话就坚持吧

11月 05

0.00 avg. rating (0% score) - 0 votes

题目大意

给你一张n个点,m条边的无向联通图,你从1号点出发,沿着边随意走动,走到n号点停止。走过边的价值为这条边的编号。让你给边从1~m标号,使价值的期望最大。


显然最终答案是
\sum _{i=1}^m val[i] \cdot p[i]
如果我们知道p数组,那么就可以贪心的匹配val值。
思考边被走的概率。
显然是他所连接两个点被走的期望次数/每个点的度数的和。
p[i]=\frac{E[i_u]}{du[i_u]}+ \frac{E[i_v]}{du[i_v]}

显然度数一直,我们要求的是期望次数,
显然对于点x的期望次数是
E[x]=∑_y \frac{E[y]}{du[y]}
发现这是个线性方程组,直接高斯消元。
注意对于1号和n号点不是这样,
显然1号点要+1,n号点就是1.

代码

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const int N=505;
const double esp=1e-9;

int n,m;
int xx[N*N],yy[N*N];
int du[N];
double mat[N][N],val[N*N],ans;
bool cnm(double a,double b){return b>esp+a;}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) scanf("%d%d",xx+i,yy+i),du[xx[i]]++,du[yy[i]]++;
    for(int i=1;i<=m;++i)
    {
        if(xx[i]!=n) mat[yy[i]][xx[i]]=1.0/(double)du[xx[i]];
        if(yy[i]!=n) mat[xx[i]][yy[i]]=1.0/(double)du[yy[i]];
    }
    for(int i=1;i<=n;++i) mat[i][i]=-1;
    mat[1][n+1]=-1;
    for(int i=1;i<=n;++i)
    {
        int tm=i;
        for(int j=i;j<=n;++j) {if(fabs(mat[j][i])>fabs(mat[tm][i])) tm=j;}
        if(tm!=i) for(int j=1;j<=n+1;++j) swap(mat[i][j],mat[tm][j]);
        for(int j=i+1;j<=n;++j)
        {
            double x=mat[j][i]/mat[i][i];
            for(int k=i;k<=n+1;++k) mat[j][k]-=mat[i][k]*x;
        }
    }
    for(int i=n;i>=1;--i)
    {
        for(int j=i+1;j<=n;++j) mat[i][n+1]-=mat[i][j]*mat[j][n+1];
        mat[i][n+1]/=mat[i][i];
    }
    for(int i=1;i<=m;++i)
    {
        int x=xx[i],y=yy[i];
        if(x!=n) val[i]+=mat[x][n+1]/(double)du[x];
        if(y!=n) val[i]+=mat[y][n+1]/(double)du[y];
    }
    sort(val+1,val+1+m,cnm);
    for(int i=1;i<=m;++i) ans+=val[i]*(m-i+1);
    printf("%.3lf",ans); 
}
0.00 avg. rating (0% score) - 0 votes
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注