本文共 1491 字，大约阅读时间需要 4 分钟。
Description
一个无向图，节点1有一个炸弹，在每个单位时间内，有可能在这个节点炸掉，也有p/q的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。
bzoj权限题,题目大概是机翻?
bzoj3270的双倍经验题(然而我大于小于分不清楚还WA了一发)
//%std#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define lovelive long long#define lc son[x][0]#define rc son[x][1]#define lowbit(x) (x&(-x))#define pt vc#define P(x,y) ((x)*n-n+y)const int N=300+30;void read(int &x){ int p=1; x=0; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') p=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-48; c=getchar(); } x*=p;}double f[N][N],ans[N];int mp[N][N],d[N];void gauss(int n){ int k; double tmp; for(int i=1;i =1;i--) { ans[i]=f[i][n+1]/f[i][i]; for(int j=i-1;j>=1;j--) f[j][n+1]-=ans[i]*f[j][i]; }}int main(){// freopen("testdata.in","r",stdin);// freopen("testdata.out","w",stdout); int n,m,a,b,x,y; double p; read(n);read(m);read(a);read(b); p=a*1.0/b; for(int i=1;i<=m;i++) { read(x);read(y); mp[x][y]=mp[y][x]=1; ++d[x];++d[y]; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]) f[i][j]=(1-p)/d[j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=-f[i][j]; for(int i=1;i<=n;i++) f[i][i]+=1; f[1][n+1]=1; gauss(n); for(int i=1;i<=n;i++) printf("%.9lf\n",ans[i]*p); return 0;}
听说bzoj坑点很多
但是我在luogu上交的很顺利
转载于:https://www.cnblogs.com/NicoDafaGood/p/8849539.html
