首页 > 代码库 > 游走（bzoj 3143）

游走（bzoj 3143）

2024-08-31 10:11:35   219人阅读

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。
/*
  研究了好长时间，仍然没有弄懂这样建立方程组的原理
  不过借机搞了搞高斯消元 
  一个网址：http://jingyan.baidu.com/article/39810a23e40c80b636fda63a.html
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 510
#define M 250010
using namespace std;
double a[N][N],x[N],w[M],ans;
int u[M],v[M],d[N],n,m;
void Gauss(int n,int m){
    int i,j,k;
    //为方便后面的操作，找到col这列中最大的数，并把它所在的行换到第一列
    for(i=1;i<=m;i++){
        for(k=i,j=i+1;j<=n;j++)
            if(fabs(a[k][i])<fabs(a[j][i]))
        if(i!=k)
            for(j=i;j<=m;j++)
                swap(a[i][j],a[k][j]);
        //利用第一个的式子消元 
        for(j=i+1;j<=n;j++){
            double tmp=a[j][i]/a[i][i];
            for(k=i;k<=m;k++)
                a[j][k]-=a[i][k]*tmp;
        }
    }
    //计算唯一解
    for(i=m-1;i;i--){
        double tmp=0;
        for(j=i+1;j<m;j++)
            tmp+=a[i][j]*x[j];
        x[i]=(a[i][m]-tmp)/a[i][i];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        d[u[i]]++;d[v[i]]++;
    }
    for(int i=1;i<n;i++) a[i][i]=-1;
    for(int i=1;i<=m;i++){
        a[u[i]][v[i]]+=1.0/d[v[i]];
        a[v[i]][u[i]]+=1.0/d[u[i]];
    }
    for(int i=1;i<=n;i++) a[n][i]=0;
    a[1][n+1]=-1;a[n][n]=1;
    Gauss(n,n+1);
    for(int i=1;i<=m;i++)
        w[i]=x[u[i]]/d[u[i]]+x[v[i]]/d[v[i]];
    sort(w+1,w+m+1);
    double ans=0;
    for(int i=1;i<=m;i++)
        ans+=(m-i+1)*w[i];
    printf("%.3lf\n",ans);
    return 0;
}

 

游走（bzoj 3143）


联系
我们