【bzoj1778】驱逐猪猡

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

这种题目算是一种讨论题，给了我们很多关于用高斯消元求解带环$dp$的启示

设向量$T(i)=${$x_1,x_2,……,x_n$}表示 $i$ 时刻在点 $x$ 爆炸的概率

我们构造转移矩阵 $E_{i,j}$ 表示从 $j$ 转移到 $i$ 的概率

则$E_{i,j}=\sum (1-\frac{P}{Q}) \times \frac{1}{d_j}$

那么最终的答案向量$ans=\frac{P}{Q} \times T_0 (E^0+E^1+E^2+……)= \frac{P}{Q} \times T_0 \times \frac{I}{I-E}$ (I为单位矩阵)

如果你想用矩阵求逆的话直接做就行了，但是这里我们用高斯消元来做：

把分母移到左边得：$(I-E) \times ans = \frac{P}{Q} \times T_0 \times I$

然后就符合高斯消元的套路了：(I-E)是系数矩阵，ans是答案向量

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
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-10
using namespace std;
struct node{int x,y;}e[50010];
double a[305][305];
int n,m,p,q,d[305];
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 init(){
	n=read();  m=read();  p=read();  q=read();
	double rate=(double)p/q;
	for(int i=1;i<=m;++i){
		e[i].x=read();  e[i].y=read();
		d[e[i].x]++;  d[e[i].y]++;
	}
	for(int i=1;i<=m;++i){
		a[e[i].x][e[i].y]+=(rate-1)/d[e[i].y];
		a[e[i].y][e[i].x]+=(rate-1)/d[e[i].x];
	}
	for(int i=1;i<=n;++i) a[i][i]+=1.0;
	a[1][n+1]=rate;
}
bool gauss(){
	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 putout(){
	for(int i=1;i<=n;++i) printf("%.9lf\n",a[i][n+1]);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	init(); gauss(); putout();
	return 0;
}

本文标题:【bzoj1778】驱逐猪猡

文章作者:chty

发布时间:2017年03月12日 - 08时52分

最后更新:2018年03月02日 - 17时29分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,