题意:

给定一个无向有环图(可能有重边),给每一条边编号为1~m的不重数值,现在从1号节点出发,随机访问相邻节点,得分加上经过的边的编号,到达n号节点终止,求通过合理编号,到达n号节点时得分期望的最小值。(n<=500)

思路:

1.对于每一个节点,我们可以通过高斯消元求出它经过次数的期望值。初始时1号节点期望为1,n号节点期望为0,列一个方程组就可以求出经过次数的期望值p[i]。
2.对于每一条边的期望经过次数,有$e[i]=\sum{\frac{p[u]}{d[u]}}+\sum{\frac{p[v]}{d[v]}}$其中u,v是边i的两端点,d[i]为点i的度。
3.我们需要明确一个事实:对于两个相同长度的序列,其中一个升序排列,当这两个序列排在相同位置的元素的积的和取最小值时,当且仅当另一个序列是降序排列的。
证明:从二元组(a1,a2),(b1,b2)着手,如果有a1<a2,b1<b2,那么s1=(a1,a2)(b1,b2)=a1b1+a2b2,设s2=(a1,a2)(b2,b1)=a1b2+a2b1,∴s1-s2=a1(b1-b2)+a2(b2-b1)=(b1-b2)(a1-a2)>0,∴a1>a2。我们可以大胆地想,这个结论推广到n元组也是适用的。因为两个n元组的积一定可以表示为很多个满足上述规律的二元组的积的加减嵌套。
4.当我们知道了每一条边的经过次数和其编号,答案所有边编号与次数的积的和。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

#define ldabs(a) (a<0?-a:a)
#define MX 1000

using namespace std;

typedef long double ldb;

ldb mat[MX][MX],ans[MX],eep[MX];
int n,m,fst[MX],nxt[MX*MX],u[MX*MX],v[MX*MX],w[MX*MX],lnum,dnum[MX];

void addeg(int nu,int nv)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum,u[lnum]=nu,v[lnum]=nv;
}

void input()
{
    memset(fst,0xff,sizeof(fst));
    int a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        addeg(a,b);
        dnum[a]++,dnum[b]++;
    }
}

void createmat1()
{
    for(int i=1;i<=n-1;i++)
    {
        for(int j=fst[i];j!=-1;j=nxt[j])
        {
            mat[i][v[j]]+=-(1.0/(ldb)dnum[v[j]]);
            mat[v[j]][i]+=-(1.0/(ldb)dnum[i]);
        }
        mat[i][0]=0;
        mat[i][i]=1;
    }
    mat[1][0]=1;
}

pair<int,int>src[MX*MX];

void gauss()
{
    int mxpos;
    ldb trans,now;
    for(int i=1;i<=n-1;i++)
    {
        mxpos=i;
        for(int j=i;j<=n-1;j++)
            if(ldabs(mat[j][i])>ldabs(mat[mxpos][i]))
                mxpos=j;
        swap(mat[i],mat[mxpos]);
        for(int j=i+1;j<=n-1;j++)
        {
            trans=mat[j][i]/mat[i][i];
            if(ldabs(trans)<0.0000001)continue;
            for(int k=0;k<=n-1;k++)mat[j][k]-=mat[i][k]*trans;
        }
    }
    ans[n]=0;
    for(int i=n-1;i>=1;i--)
    {
        now=mat[i][0];
        for(int j=i+1;j<=n;j++)now-=mat[i][j]*ans[j];
        now/=mat[i][i];
        ans[i]=now;
    }
}

void calcans()
{
    ldb tot=0;
    for(int i=1;i<=lnum;i++)eep[i]=ans[u[i]]/(ldb)dnum[u[i]]+ans[v[i]]/(ldb)dnum[v[i]];
    sort(eep+1,eep+lnum+1);
    for(int i=1;i<=lnum;i++)tot+=eep[i]*(double)(lnum-i+1);
    printf("%.3f\n",(double)tot);
}

int main()
{
    input();
    createmat1();
    gauss();
    calcans();
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

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

你是机器人吗? =。= *