【bzoj3270】博物馆

  • 高斯消元重修系列第五题

有了上一题【驱赶猪猡】的经验,这道题的大致做法就很显然了

但是,这道题是两个人,怎么办?

蒟蒻想不出解决方法,于是只能去膜拜POPOQQQ大爷的方法:

用一个状态表示一个点对(x,y)

这样在转移时可以用点之间的转移推出状态间的转移(具体看代码)

在找答案时可以直接找(i,i)对应的状态的答案

时间复杂度(n^6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-8
#define MAXN 405
using namespace std;
struct node{int y,next;}e[805];
int n,m,len,st1,st2,Link[MAXN],d[MAXN];
double p[MAXN],a[MAXN][MAXN];
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
int get(int i,int j) {return (i-1)*n+j;}
void init(){
n=read(); m=read(); st1=read(); st2=read();
for(int i=1;i<=m;++i){
int x=read(),y=read();
insert(x,y); insert(y,x);
d[x]++; d[y]++;
}
for(int i=1;i<=n;++i) scanf("%lf",&p[i]);
for(int x=1;x<=n;++x)for(int y=1;y<=n;++y)if(x!=y){
a[get(x,y)][get(x,y)]-=p[x]*p[y];
for(int i=Link[x];i;i=e[i].next)
a[get(x,y)][get(e[i].y,y)]-=(1-p[x])/d[x]*p[y];
for(int i=Link[y];i;i=e[i].next)
a[get(x,y)][get(x,e[i].y)]-=(1-p[y])/d[y]*p[x];
for(int i=Link[x];i;i=e[i].next)
for(int j=Link[y];j;j=e[j].next)
a[get(x,y)][get(e[i].y,e[j].y)]-=(1-p[x])/d[x]*(1-p[y])/d[y];
}
for(int i=1;i<=n*n;++i)
for(int j=1;j<i;++j)
swap(a[i][j],a[j][i]);
for(int i=1;i<=n*n;++i) a[i][i]+=1;
a[get(st1,st2)][n*n+1]=1;
}
bool gauss(int n){
int now=1;
for(int i=1,temp;i<=n;++i){
for(temp=now;temp<=n;++temp) if(fabs(a[temp][i])>eps) break;
if(temp>n) continue;
if(temp!=now) swap(a[temp],a[now]);
double t=a[now][i];
for(int j=i+1;j<=n+1;++j) a[now][j]/=t;
for(int j=1;j<=n;++j)if(j!=now){
double t=a[j][i];
for(int k=i+1;k<=n+1;++k) a[j][k]-=t*a[now][k];
}
++now;
}
for(int i=now;i<=n;++i) if(fabs(a[i][n+1])>eps) return 0;
return 1;
}
void solve(){
gauss(n*n);
for(int i=1;i<=n;++i) printf("%.6lf ",a[get(i,i)][n*n+1]);
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
init(); solve();
return 0;
}
文章目录
,