首页 > 代码库 > hackerrank Alex对战Fedor
hackerrank Alex对战Fedor
任意门
为了在漫长得飞行旅途中娱乐,Alex和Fedor发明了如下的一个简单的双人游戏。游戏是:
-
首先, Alex画一个有权无向图。该图中可能有多重边(多重边的权值可能相同或者不同)。
-
然后,Fedor选取该图的一个生成树。如果该树是这个图的最小生成树,则Fedor获胜。否则,Alex获胜。
如果两棵树分别包含的边标号形成的两个集合不相同,我们认为这两棵树不同。两个集合A和B,如果至少存在一个元素在A中但不在B中,或者反之,至少存在一个元素在B中但不在A中,则我们认为这两个集合不同。
我们还要指出图拥有太多的生成树会让Alex和Fedor烦乱,于是他们不会用多于$10^{18}$棵生成树的图进行游戏。
现在, Fedor懒得找最小生成树了,于是他会任选一个Alex的图的生成树。每棵生成树被Fedor选择的概率相同。请问此时Fedor获胜的概率是多少?
裸的矩阵树定理,但是这玩意卡精度,卡了我一个多小时……把long double换成__float128就过了,要是还卡估计就得强行取模+CRT了。
#include<cassert> #include<cstdio> #include<cstring> #include<algorithm> #define MN 401 #define ld __float128 #define ll long long #define int long long using namespace std; int read_p,read_ca,read_f; inline int read(){ read_p=0;read_ca=getchar();read_f=1; while(read_ca<‘0‘||read_ca>‘9‘) read_f=read_ca==‘-‘?-1:read_f,read_ca=getchar(); while(read_ca>=‘0‘&&read_ca<=‘9‘) read_p=read_p*10+read_ca-48,read_ca=getchar(); return read_p*read_f; } struct na{int x,y,z;}b[MN]; bool operator < (na a,na b){return a.z<b.z;} int n,m,a[MN][MN],fa[MN],s[MN]; ll mmh,MMH,o; ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} ld _abs(ld x){return x<0?-x:x;} ll gauss(int n){ static ld b[MN][MN]; int i,j,k; ld x=1; for (i=2;i<=n;i++) for (j=2;j<=n;j++) b[i][j]=a[i][j]; for (i=2;i<=n;i++){ for (j=i;j<=n;j++) if (_abs(b[j][i])>_abs(b[i][i])) for (k=i;k<=n;k++) swap(b[j][k],b[i][k]); for (j=i+1;j<=n;j++){ ld s=b[j][i]; for (k=i;k<=n;k++) b[j][k]-=b[i][k]/b[i][i]*s; } x*=b[i][i]; } return (ll)(_abs(x)+0.5); } int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);} inline void add(int x,int y){x=gf(x);y=gf(y);fa[x]=y;} bool cmp(na a,na b){return gf(a.x)<gf(b.x);} inline ll work(int l,int r){ for (int i=1;i<=n;i++) s[i]=0; for (int i=l;i<r;i++) if (b[i].x!=b[i].y) s[b[i].x]=1,s[b[i].y]=1; for (int i=1;i<=n;i++) s[i]+=s[i-1]; for (int i=1;i<=s[n];i++) for (int j=1;j<=s[n];j++) a[i][j]=0; memset(a,0,sizeof(a)); for (int i=l;i<r;i++) if (b[i].x=s[b[i].x],b[i].y=s[b[i].y],b[i].x!=b[i].y) a[b[i].x][b[i].y]--,a[b[i].y][b[i].x]--,a[b[i].x][b[i].x]++,a[b[i].y][b[i].y]++; return gauss(s[n]); } ll Mavis(){ ll mmh=1; sort(b+1,b+1+m); for (int i=1,j=1;i<=m;i=j){ while (b[j].z==b[i].z&&j<=m) j++; for (int k=i;k<j;k++) b[k].x=gf(b[k].x),b[k].y=gf(b[k].y); for (int k=i;k<j;k++) add(b[k].x,b[k].y); sort(b+i,b+j,cmp); for (int k=i,l=i;k<j;k=l){ while (l<j&&gf(b[l].x)==gf(b[k].x)) l++; mmh*=work(k,l); } } for (int i=2;i<=n;i++) if (gf(i)!=gf(1)) return 0; return mmh; } signed main(){ n=read();m=read(); for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=m;i++) b[i].x=read(),b[i].y=read(),b[i].z=read(), a[b[i].x][b[i].y]--,a[b[i].y][b[i].x]--,a[b[i].x][b[i].x]++,a[b[i].y][b[i].y]++; mmh=gauss(n);MMH=Mavis();o=gcd(mmh,MMH);if (o) mmh/=o,MMH/=o; printf("%lld/%lld\n",MMH,mmh); }
hackerrank Alex对战Fedor
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。