首页 > 代码库 > bzoj 3143: [Hnoi2013]游走 高斯消元

bzoj 3143: [Hnoi2013]游走 高斯消元

2024-08-03 22:25:27   220人阅读

3143: [Hnoi2013]游走

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1026  Solved: 448
[Submit][Status]

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。
 
 
　　这道题我又把题目看错了，我最开始看成了有向无环图，【目测世纪大水题】。。。
　　当这种期望题出现环之后，就变的复杂很多，我们可以对于每一个点求出它的期望经过次数p[]，则p[i]=segma(p[j]/d[j])，有一点还是有点不清楚，就是为什么p[1]在上述式子上必须恰好加1，就只好姑且先记住这样的结论吧。
　　有了上述思路，就可以用高斯消元来做了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 1000#define MAXV MAXN#define MAXE 500000#define abs(x) ((x)>0?(x):(-(x)))typedef long double real;struct Edge{        int np;        Edge *next;}E[MAXE],*V[MAXV];int tope=-1;void addedge(int x,int y){        E[++tope].next=V[x];        E[tope].np=y;        V[x]=&E[tope];}int deg[MAXN];int q[MAXN];real pp[MAXN];real a[MAXN][MAXN];int n,m;struct edge{        int x,y;        real p;}w[MAXE];bool cmp_p(edge e1,edge e2){        return e1.p>e2.p;}void pm(){        for (int i=1;i<n;i++)        {                for (int j=1;j<=n;j++)                {                        printf("%.2Lf ",a[i][j]);                }                printf("\n");        }        printf("\n");}int main(){        freopen("input.txt","r",stdin);        int i,j,k,x,y,z;        scanf("%d%d",&n,&m);        for (i=0;i<m;i++)        {                scanf("%d%d",&x,&y);                addedge(x,y);                addedge(y,x);                deg[x]++;deg[y]++;                w[i].x=x;w[i].y=y;        }        int now;        Edge *ne;        for (i=1;i<=n-1;i++)        {                now=i;                for (ne=V[now];ne;ne=ne->next)                {                        if (ne->np!=n)                                a[now][ne->np]=1.0/deg[ne->np];                }                a[now][now]=-1;                a[now][n]=0;        }        a[1][n]=1;        //pm();        for (i=1;i<=n-1;i++)        {                x=i;                for (j=i+1;j<=n-1;j++)                {                        if (abs(a[j][i])>abs(a[x][i]))                        {                                x=j;                        }                }                if (x!=i)                {                        for (j=i;j<=n;j++)                        {                                swap(a[i][j],a[x][j]);                        }                }                if (!a[i][i])continue;                for (j=i+1;j<=n-1;j++)                {                        real t=a[j][i]/a[i][i];                        for (k=i;k<=n;k++)                        {                                a[j][k]-=t*a[i][k];                        }                }                //pm();        }        pp[n]=1;        for (i=n-1;i>=1;i--)        {                for (j=i+1;j<=n;j++)                {                        pp[i]-=pp[j]*a[i][j];                }                pp[i]/=a[i][i];        }        pp[n]=0;/*        for (i=1;i<=n;i++)                printf("%.2Lf ",pp[i]);        printf("\n");*/        for (i=0;i<m;i++)        {                w[i].p=pp[w[i].x]/deg[w[i].x] + pp[w[i].y]/deg[w[i].y];        }        sort(w,w+m,cmp_p);        int head=-1,tail=-1;        real ans=0;        for (i=0;i<m;i++)        {                ans+=(i+1)*w[i].p;        }        printf("%.3Lf",ans);}

 

bzoj 3143: [Hnoi2013]游走 高斯消元


联系
我们