Rockdu's Blog

  T国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。
    在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。
    辛运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。

  输入的第一行包含整数N。
  接下来N行，每行N个实数，第i+l行，列的数G[i][j]表示城市i与j之
间仍有道路联通的概率。
    输入保证G[i][j]=G[j][i]，且G[i][j]=0；G[i][j]至多包含两位小数。

    输出一个任意位数的实数表示答案。
    你的答案与标准答案相对误差不超过10^(-4)即视为正确。

1 < N < =50

数据保证答案非零时，答案不小于10^-4

Round 1 Day 2

首先我们要知道，矩阵树定理求的其实是每一种生成树边权乘积的和。

但是我们发现，对于一种生成树，我们要算的是树内都被选的概率乘上树外都不被选的概率，涉及到了生成树外的边。

但是仔细想想就会发现，其实树外面全都不选的概率乘上树里面全都不选的概率就是整棵树都不选的概率，我们用全都不选的概率除以树内都不选的概率就得到了树外不选的概率。这样我们提出全部都不被选的概率，于是矩阵只和树内的边有关。因此给每条边附上p / (1-p)的权值，就可以直接矩阵树定理了。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
 
const int maxn = 55;
double mat[maxn][maxn];
double e[maxn][maxn];
int n;
 
double Gauss(int n) {
    int pos = -1;
    double mx = 0, Kn = 0;
    For(i, 1, n) {
        pos = -1, mx = 0;
        For(j, i, n) {
            if(abs(mat[j][i]) > mx)
                pos = j, mx = abs(mat[j][i]);
        }
        if(!~pos) continue;
        swap(mat[pos], mat[i]);
        For(j, 1, n) {
            if(j == i) continue;
            Kn = mat[j][i] / mat[i][i];
            For(k, 1, n) mat[j][k] -= mat[i][k] * Kn;
        }
    }
    double ans = 1;
    For(i, 1, n) ans *= mat[i][i];
    return ans;
}
 
int main() {
    scanf("%d", &n);
    For(i, 1, n) 
        For(j, 1, n) {
            scanf("%lf", &e[i][j]);
            if(j != i) {
                mat[i][j] = - e[i][j] / (1 - e[i][j]);
                mat[i][i] -= mat[i][j];
            }
        }
    double oans = Gauss(n - 1);
    For(i, 1, n) 
        For(j, i + 1, n)
            oans *= (1 - e[i][j]);
    cout << oans;
    return 0;
}