《P2973 [USACO10HOL] Driving Out the Piggies G》
题目描述
奶牛们制造了一种随机臭弹，目的是驱赶小猪。小猪文明由 N(2≤N≤300) 个小猪城市组成，这些城市编号为 1 到 N，通过 M(1≤M≤44,850) 条双向道路连接，具体由它们的不同端点 Aj 和 Bj 指定 (1≤Aj≤N;1≤Bj≤N)。小猪城市 1 总是与至少一个其他城市相连。
臭弹在小猪城市 1 部署。每小时（包括第一小时），它有 P/Q(1≤P≤1,000,000,1≤Q≤1,000,000;P≤Q) 的概率爆炸并污染它所在的城市。如果它没有爆炸，它会随机选择一条通往其他城市的道路并沿着它走，直到到达一个新城市。所有从一个城市出发的道路被选择的概率相同。
由于臭弹的随机性质，奶牛们想知道哪些城市最有可能被污染。给定小猪文明的地图以及臭弹在每个小时内爆炸的概率，计算每个城市被污染的概率。
例如，假设小猪文明由两个城市组成并且相连，臭弹从城市 1 开始，每次进入一个城市时有 21 的概率爆炸：
1--2
我们有以下可能的臭弹路径（最后一个城市是终点城市）：
1: 1
2: 1-2
3: 1-2-1
4: 1-2-1-2
5: 1-2-1-2-1
等等。 要找到臭弹最终停留在城市 1 的概率，我们可以将上述每条路径的概率相加（具体来说，就是上述列表中每一个奇数编号的路径）。选择第 k 条路径的概率正好是 (1/2)k ——臭弹必须在前 k−1 次不留在它的城市（每次概率为 1−21=21），然后在最后一个城市停留（概率为 21）。
因此，我们在城市 1 停留的概率由无穷级数 2∤k∑(21)k 表示。当我们无限地求和这些项时，最终得到的概率恰好是 32，大约为 0.666666667。这意味着在城市 2 停留的概率是 31，大约为 0.333333333。
输入格式
第 1 行：四个用空格分隔的整数：N,M,P,Q。
第 2 行到第 M+1 行：第 i+1 行描述一条道路，包含两个用空格分隔的整数：Aj 和 Bj。
输出格式
第 1 行到第 N 行：在第 i 行，输出城市 i 被摧毁的概率，格式为浮点数。绝对误差最多为 10−6 的答案将被接受（注意，您应该输出至少 6 位小数以满足此要求）。
显示翻译
题意翻译
输入输出样例
输入 #1复制
2 1 1 2 1 2
输出 #1复制
0.666666667 0.333333333
说明/提示
感谢 @Alpha 贡献 Special Judge。
代码实现：
#include<bits/stdc++.h> using namespace std; inline int read() { char ch=getchar();int x=0;bool f=0; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1; for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48); if(f==1)x=-x;return x; } const int mn=200005; struct ed { int v, nex; } e[mn]; int n, m, u, v, hd[mn], cnt=0, deg[505]; double a[505][505], p, q; void add(int u, int v) { e[++cnt].v=v;e[cnt].nex=hd[u];hd[u]=cnt; } int main() { n=read(),m=read();cin>>p>>q; for(int i=1;i<=m;i++) u=read(),v=read(),add(u,v),add(v,u),deg[u]++,deg[v]++; a[1][n+1]=-p/q; for(int i=1;i<=n;i++) { a[i][i]=-1; for(int j=hd[i];j;j=e[j].nex) { int to=e[j].v; a[i][to]=1.0/deg[to]*(q-p)/q; } } for(int i=1;i<=n;++i) { int mid=i; for(int j=i+1;j<=n;++j) if(fabs(a[j][i])>fabs(a[mid][i])) mid=j; for(int j=1;j<=n+1;++j) swap(a[i][j],a[mid][j]); for(int j=1;j<=n;++j) { if(j!=i) { double t=a[j][i]/a[i][i]; for(int k=i+1;k<=n+1;++k) a[j][k]-=a[i][k]*t; } } } for(int i=1;i<=n;++i) printf("%.9lf\n",a[i][n+1]/a[i][i]); return 0; }