P3317 [SDOI2014]重建 变元矩阵树定理 高斯消元

传送门:https://www.luogu.org/problemnew/show/P3317

这道题的推导公式还是比较好理解的,但是由于这个矩阵是小数的,要注意高斯消元方法的使用;

#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> /* ⊂_ヽ
  \\ Λ_Λ 来了老弟
   \('ㅅ')
    > ⌒ヽ
   /   へ\
   /  / \\
   レ ノ   ヽ_つ
  / /
  / /|
 ( (ヽ
 | |、\
 | 丿 \ ⌒)
 | |  ) /
'ノ )  Lノ */ using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c); const ll oo = 1ll<<;
const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;} /*-----------------------showtime----------------------*/
const int maxn = ;
double mp[maxn][maxn];
double a[maxn][maxn]; int n; double Gauss(int n){
for(int i=; i<n; i++){
int mx = i;
for(int j=i+; j<n; j++){
if(fabs(a[mx][i]) < fabs(a[j][i])) mx = j;
}
swap(a[i], a[mx]);
for(int j=i+; j<n; j++){
double tmp = a[j][i]/a[i][i];
for(int k=i+; k<n; k++)
a[j][k] -= a[i][k] * tmp;
}
}
double ans = ;
for(int i=; i<n; i++) ans *= a[i][i];
return fabs(ans);
} int main(){
scanf("%d", &n);
double tmp = ;
for(int i=; i<=n; i++) {
for(int j=; j<=n; j++) {
scanf("%lf", &mp[i][j]);
if(fabs(1.0 - mp[i][j]) < esp) mp[i][j] = 1.0- esp;
if(i < j)tmp = tmp * (1.0-mp[i][j]);
mp[i][j] = mp[i][j] / (1.0 - mp[i][j]);
}
} for(int i=; i<=n; i++){
for(int j=i+; j<=n; j++){
a[i][j] = a[j][i] = -mp[i][j];
a[i][i] += mp[i][j];
a[j][j] += mp[i][j];
}
}
printf("%.10f\n", Gauss(n) * tmp);
return ;
}
上一篇:openstack私有云布署实践【12.1 网络Neutron-controller节点配置(科兴环境)】


下一篇:IntelliJ IDEA 第一个 Scala 程序