下半年也要继续努力啊
# 题意
> 洛谷P3317
点击展开/折叠题面
T国有 $N$ 个城市,用若干双向道路连接。一对城市之间至多存在一条道路。
在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到现在几乎没有消息传回。
幸运的是,此前 T 国政府调查过每条道路的强度,现在他们希望只利用这些信息估计灾情。具体地,给定每条道路在洪水后仍能通行的概率,请计算仍能通行的道路恰有 $N−1$ 条,且能联通所有城市的概率。
# 解析
形式化地表达一下我们要求的东西:
其中 T 是生成树。
我们发现,把 $p_i$ 作为边权,简单地套用 Matrix-Tree 定理,可以计算出 $\sum\limits_{T}\prod\limits_{i\in T}p_i$。考虑怎么补上后面的一个 Prod。
发现比较难直接统计在生成树外的乘积,但是我们可以间接地——在所有边权的乘积里除去在生成树里的边权的乘积。于是式子就变得非常简单了:
那么把 $\frac{p_i}{1-p_i}$ 作为边权,用Matrix-Tree跑就可以了。
但是有一个小细节,我们发现 $p_i=0$ 或 $p_i=1$ 时比较特殊。$p_i=0$ 时分子可能为 $0$,不过这不影响;$p_i=1$ 会让分母为 $0$,这影响就大了。$p_i=1$ 就是这条边一定会选,那么我们预先把这些必选的边连成的连通块缩点(用并查集),注意判断是否必选的边就已经有 circle 了。
# 源代码
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int N=55; const double EPS=1e-7;
int n; double mat[N][N],A[N][N]; int sot[N];
inline double ABS(const double &a){return a<0? -a:a;} double Det(int siz){ double ret=1; for(int i=1;i<siz;i++){ int it=-1;double tit=-1; for(int j=i;j<siz;j++) if(ABS(mat[j][i])>tit){ tit=ABS(mat[j][i]); it=j; } if(tit<EPS) return 0; if(it!=i){ for(int j=i;j<siz;j++) swap(mat[i][j],mat[it][j]); ret=-ret; } ret*=mat[i][i]; for(int j=i+1;j<siz;j++){ if(ABS(mat[j][i])<EPS) continue; double mul=mat[j][i]/mat[i][i]; for(int k=i;k<siz;k++) mat[j][k]-=mat[i][k]*mul; } } return ret; } struct DSU{ int fa[N]; int FindFa(int u){return u==fa[u]? u:fa[u]=FindFa(fa[u]);} bool Merge(int u,int v){ u=FindFa(u),v=FindFa(v); if(u==v) return false; fa[u]=v; return true; } void Init(int siz){ for(int i=0;i<=siz;i++) fa[i]=i; } }Ds; int main(){ scanf("%d",&n); Ds.Init(n); double all=1; bool ncir=true; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%lf",&A[i][j]); if(i<j){ if(ABS(1-A[i][j])<EPS) ncir&=Ds.Merge(i,j); else all*=(1-A[i][j]); } } if(!ncir){ printf("0\n"); return 0; } int nsot=0; for(int i=1;i<=n;i++){ int fai=Ds.FindFa(i); if(!sot[fai]) sot[fai]=++nsot; } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ int u=sot[Ds.FindFa(i)],v=sot[Ds.FindFa(j)]; if(u==v) continue; A[i][j]/=(1-A[i][j]); mat[u][u]+=A[i][j]; mat[v][v]+=A[i][j]; mat[u][v]-=A[i][j]; mat[v][u]-=A[i][j]; } printf("%.6f\n",Det(nsot)*all); return 0; }
|
THE END
Thanks for reading!