BZOJ 3143 游走 高斯消元

题目链接：

中文题目。
F(v) 表示小Z在图上游走时，在v点走的次数
这样就可以根据图上的链接关系 构造出N个方程在求解既可

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 500 + 5;
const double eps = 1e-4;
typedef double Matrix[maxn][maxn];
Matrix A;
bool adj[maxn][maxn];
int n,m,ous[maxn];
struct edge{
    int u,v;
    double p;
    bool operator<(edge o)const{
        return p > o.p;
    }
}edges[maxn * maxn];
void INIT(){
    memset(adj,0,sizeof adj);
    memset(ous,0,sizeof ous);
    memset(A,0,sizeof A);
}
void Gauss(){
    int i,j,k,p;
    for(i = 0;i < n;++i){
        k = i;
        for(p = i + 1;p < n;++p) if( fabs(A[p][i]) > fabs(A[k][i]) ) k = p;
        if(k != i) for(p = 0;p <= n;++p) swap(A[i][p],A[k][p]);
        for(k = i + 1;k < n;++k){
            double tmp = A[k][i] / A[i][i];
            for(p = i;p <= n;++p) A[k][p] = A[k][p] - tmp * A[i][p];
        }
    }
    for(j = n - 1;j >= 0;--j){
        double tmp = 0;
        for(k = j + 1;k < n;++k) tmp += A[j][k] * A[k][n];
        A[j][n] = (A[j][n] - tmp) / A[j][j];
    }
}

int main(){
    INIT();
    scanf("%d%d", &n,&m);
    for(int i = 0;i < m;++i){
        scanf("%d%d",&edges[i].u,&edges[i].v);
        edges[i].v--,edges[i].u--;
        ous[edges[i].u]++;
        ous[edges[i].v]++;
        adj[edges[i].u][edges[i].v] = adj[edges[i].v][edges[i].u] = 1;
    }
    n--;
    //构造方程
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            if(adj[j][i]){
                A[i][j] = 1.0 / ous[j];
            }
        }
        A[i][i] -= 1.0;
    }
    A[0][n] = -1.0;

    //高斯消元
    Gauss();
    for(int i = 0;i < m;++i){
        int v = edges[i].v,u = edges[i].u;
        edges[i].p = A[v][n] / ous[v] + A[u][n] / ous[u];
    }
    sort(edges,edges + m);
    double ans = 0;
    for(int i = 0;i < m;++i){
        ans += edges[i].p * (i + 1);
    }
    printf("%.3f\n",ans);
    return 0;
}