题解 CF113D 【Museum】
officeyutong
2018-10-30 20:00:12
```cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <iomanip>
#define debug(x) std::cout << #x << " = " << x << std::endl;
typedef int int_t;
typedef long double real_t;
const int_t LARGE = 22;
const real_t EPS = 1e-6;
using std::cin;
using std::endl;
using std::cout;
real_t mat[501][501];
bool graph[23][23];
int_t degree[LARGE + 1];
real_t prob[LARGE + 1];
int_t n,m,a,b;
template<class T>
T xabs(T x) {
if(x<0) return -x;
return x;
}
int_t encode(int_t a,int_t b) {
// cout<<"encode "<<a<<" "<<b<<" to "<< n * (a - 1) + b - ((a>b)?(a-1):a)<<endl;
return n * (a - 1) + b - ((a>b)?(a-1):a);
}
real_t cost(int_t i,int_t j ,int_t x,int_t y) {
real_t result = 0;
if(i == x && j == y) result = prob[i] * prob[j];
if(i == x && j != y) {
result = prob[i] * (1 - prob[j]) * (1.0 / degree[j]) * graph[j][y];
}
if(i != x && j == y) result = (1 - prob[i]) * (1.0 / degree[i]) * graph[i][x] * prob[j];
if(i != x && j != y) result = (1 - prob[i]) * (1.0 / degree[i]) * graph[i][x] * (1 - prob[j]) * (1.0 / degree[j]) * graph[j][y];
return result;
}
int main() {
cin >> n >> m >> a >> b;
if(a == b) {
for(int_t i=1; i<=n; i++) {
if(i==a) cout<<1<<" ";
else cout<<0<<" ";
}
return 0;
}
for(int_t i = 1; i <= m; i++) {
int_t from,to;
cin >> from >> to;
graph[from][to] = graph[to][from] = 1;
degree[from] += 1;
degree[to] += 1;
}
for(int_t i = 1 ; i <= n; i++) {
cin >> prob[i];
}
int_t len = n * n - n;
for(int_t i = 1 ; i <= n; i++) {
for(int_t j = 1; j<= n ; j++) {
if(i == j) continue;
int_t curr = encode(i,j);
mat[curr][curr] = -1;
for(int_t x = 1 ; x <= n; x++) {
for(int_t y = 1; y <= n ; y++) {
if(x == y) {
mat[curr][len + x] -= cost(i,j,x,y);
} else {
mat[curr][encode(x,y)] += cost(i,j,x,y);
}
}
}
}
}
for(int_t i = 1; i <= len; i++) {
if(xabs(mat[i][i]) < EPS) {
int_t pos = -1;
for(int_t j = i + 1; j <= len ; j++) {
if(xabs(mat[j][i]) >= EPS) {
pos = j;
break;
}
}
if(pos != -1) {
std::swap(mat[i],mat[pos]);
} else {
cout <<" exm ?? "<< endl;
return 0;
}
}
for(int_t j = i + 1; j <= len ; j++) {
real_t f = mat[j][i] / mat[i][i];
for(int_t k = i ; k <= n * n; k++) {
mat[j][k] -= f* mat[i][k];
}
}
}
for(int_t i = len ; i >=1 ; i--) {
real_t f = mat[i][i];
for(int_t j = len + 1; j <= n * n ; j++) {
mat[i][j] /= f;
}
mat[i][i] /= f;
for(int_t j = i - 1; j >= 1; j--) {
real_t f2 = mat[j][i];
mat[j][i] = 0;
for(int_t k = len + 1; k<= n * n; k++) {
mat[j][k] -= f2 * mat[i][k];
}
}
}
// print();
for(int_t i = 1; i <= n; i++) {
cout.setf(std::ios::fixed);
cout << std::setprecision(10) << mat[encode(a,b)][len + i] << " ";
}
return 0;
}
```