BZOJ3143 [Hnoi2013]游走 【高斯消元】

题目

一个无向连通图，顶点从1编号到N，边从1编号到M。

小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。

现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。

输入格式

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

输出格式

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

输入样例

3 3

2 3

1 2

1 3

输出样例

3.333

解释

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

题解

我们算出每个边的期望经过次数wi，按大到小分别赋1到M就是最优解

wi=xudegree[u]+xvdegree[v]

xi指每个点的经过次数

我们只要算出xi就可以了

对于每个点i，我们可以列出一个方程：

xi=∑j−>ijxjdegree[j]

N个方程，N个未知数，高斯消元可求解

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define eps 1e-9

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)

using namespace std;

const int maxn = 505,maxm = 500005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int G[maxn][maxn],N,M,de[maxn];

double A[maxn][maxn],X[maxn];

struct EDGE{int a,b; double w;}e[maxm];

inline bool operator <(const EDGE& a,const EDGE& b){return a.w > b.w;}

void gauss(){

    for (int i = 1; i <= N; i++){

        double t = A[i][i];

        if (fabs(t) < eps) continue;

        for (int j = i; j <= N + 1; j++) A[i][j] /= t;

        for (int j = i + 1; j <= N; j++){

            t = A[j][i];

            for (int k = i; k <= N + 1; k++)

                A[j][k] -= A[i][k] * t;

        }

    }

    for (int i = N; i > 0; i--){

        for (int j = i + 1; j <= N; j++)

            A[i][N + 1] -= X[j] * A[i][j];

        X[i] = A[i][N + 1] / A[i][i];

    }

}

int main(){

    N = RD(); M = RD();

    REP(i,M){

        de[e[i].a = RD()]++; de[e[i].b = RD()]++;

        G[e[i].a][e[i].b] = G[e[i].b][e[i].a] = true;

    }

    for (int i = 1; i < N; i++) A[i][i] = -1;

    REP(i,M){

        A[e[i].a][e[i].b] += 1.0 / de[e[i].b];

        A[e[i].b][e[i].a] += 1.0 / de[e[i].a];

    }

    for (int i = 1; i <= N; i++) A[i][N + 1] = 0;

    A[1][N + 1] = -1; A[N][N + 1] = 1; A[N][N] = 1;

    gauss();

    REP(i,M) e[i].w = X[e[i].a] / de[e[i].a] + X[e[i].b] / de[e[i].b];

    sort(e + 1,e + 1 + M);

    double ans = 0;

    REP(i,M) ans += e[i].w * i;

    printf("%.3lf",ans);

    return 0;

}