BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

2018-06-17 20:55:07来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 3597  Solved: 1618
[Submit][Status][Discuss]

Description

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

Input

第一行是正整数N和M,分别表示该图的顶点数 和边数,接下来M行每行是整数u,v(1≤u,v≤N),表示顶点u与顶点v之间存在一条边。 输入保证30%的数据满足N≤10,100%的数据满足2≤N≤500且是一个无向简单连通图。

Output

仅包含一个实数,表示最小的期望值,保留3位小数。

Sample Input

3 3
2 3
1 2
1 3

Sample Output

3.333

HINT

 

边(1,2)编号为1,边(1,3)编号2,边(2,3)编号为3。

 

Source

非官方数据

 
这题真TM恶心啊。。
思路大概是先表示出边的概率,然后表示出点的概率
发现点的概率不能直接搞
然后高斯消元搞一搞
最后贪心的加边,显然概率越小的编号应该越大
详细一点的题解在这里
https://www.luogu.org/problemnew/solution/P3232
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int MAXN=1e6+10;
const double eps=1e-7;
char buf[1<<23],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,M;
struct node
{
    int u,v,nxt;
}edge[MAXN];
int head[MAXN],num=1;
inline void AddEdge(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
double f[1001][1001],ans[MAXN],E[MAXN],inder[MAXN];
int S[MAXN],T[MAXN];
int dcmp(double x)
{
    if(x<eps&&x>-eps) return 0;
    else return x<0?-1:1;
}
void Gauss()
{

    for(int i=1;i<N;i++)
    {
        int mx=i;
        for(int j=i+1;j<N;j++)
            if( dcmp(f[j][i]-f[mx][i])>0 ) mx=j;
        if(mx!=i) swap(f[i],f[mx]);
        for(int j=i+1;j<N;j++)
        {
            double tmp=f[j][i]/f[i][i];
            for(int k=i;k<=N;k++)
                f[j][k]-=(double)tmp*f[i][k];
        }
    }
    for(int i=N-1;i>=1;i--)
    {
        for(int j=i+1;j<N;j++)
            f[i][N]-=ans[j]*f[i][j];
        ans[i]=f[i][N]/f[i][i];
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    N=read(),M=read();
    for(int i=1;i<=M;i++)
    {
        int x=read(),y=read();
        AddEdge(x,y);AddEdge(y,x);
        inder[x]++;inder[y]++;
        S[i]=x;T[i]=y;
    }
    f[1][N]=1;
    for(int i=1;i<N;i++) f[i][i]=1;
    for(int i=1;i<N;i++)
        for(int j=head[i];j!=-1;j=edge[j].nxt)
            if(edge[j].v!=N)
                f[i][edge[j].v]=(double)-1.00/inder[edge[j].v];
    Gauss();
    for(int i=1;i<=M;i++) 
        E[i]=ans[S[i]]/inder[S[i]]+ans[T[i]]/inder[T[i]];
    sort(E+1,E+M+1);
    double out=0;
    for(int i=1;i<=M;i++)
        out+=E[i]*(M-i+1);
    printf("%.3lf",out);
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:利用 MSYS2 在 Windows10 上搭建 OpenCV 开发环境

下一篇:BZOJ 1588: [HNOI2002]营业额统计