fork download
copy 
  1. #include <cstdio>
  2.  
  3. #define rep(i,j,k) for (int (i)=(j);(i)<=(k);++(i))
  4.  
  5. using namespace std;
  6.  
  7. typedef long double ld;
  8.  
  9. const int N=10,M=N*(N-1)/2,maxS=1<<N;
  10.  
  11. int n,m,all,cnt[maxS+10];
  12. ld ans,fac[M+10],C[M+10][M+10],f[maxS+10][M+10],g[maxS+10][M+10];
  13.  
  14. int main(){
  15. 	/*
  16. 	 * f[S][i]: status is S, the rank of the maximum edge of the graph is i
  17. 	 * f[S][i] = sigma(
  18. 				g[T][j] * g[S - T][i - j - 1]
  19. 				* C(i - 1, j)
  20. 				* C(cnt[S] - i, cnt[T] - j)
  21. 				* C((cnt[S] - i) - (cnt[T] - j), cnt[S - T] - (i - j - 1))
  22. 				* (cnt[S] - cnt[T] - cnt[S - T])!
  23. 			)
  24. 	 * g[S][i] = sigma(f[S][1 .. i])
  25. 	 */
  26. 	scanf("%d%d",&n,&m);
  27. 	all=1<<n;
  28. 	rep(i,1,m){
  29. 		int x,y;
  30. 		scanf("%d%d",&x,&y);
  31. 		x--; y--;
  32. 		rep(j,0,all-1) if ((j>>x&1) && (j>>y&1)) cnt[j]++;
  33. 	}
  34. 	rep(i,0,m) fac[i]=i?fac[i-1]*i:1;
  35. 	rep(i,0,m) rep(j,0,i) C[i][j]=j?C[i-1][j-1]+C[i-1][j]:1;
  36. 	rep(S,1,all-1) rep(i,0,cnt[S]){
  37. 		if (S==(S&-S)){
  38. 			f[S][i]=g[S][i]=1;
  39. 			continue;
  40. 		}
  41. 		for (int S0=S-(S&-S),T=S0;T;T=T-1&S0) rep(j,0,i-1) if (j<=cnt[T] && i-j-1<=cnt[S-T]){
  42. 			ld t=g[T][j]*g[S-T][i-j-1];
  43. 			t*=C[i-1][j];
  44. 			t*=C[cnt[S]-i][cnt[T]-j];
  45. 			t*=C[cnt[S]-i-(cnt[T]-j)][cnt[S-T]-(i-j-1)];
  46. 			t*=fac[cnt[S]-cnt[T]-cnt[S-T]];
  47. 			f[S][i]+=t;
  48. 		}
  49. 		if (i) g[S][i]=g[S][i-1]+f[S][i];
  50. 	}
  51. 	rep(i,0,m) ans+=f[all-1][i]*i;
  52. 	ans/=(m+1)*fac[m];
  53. 	printf("%.6lf\n",(double)ans);
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
7 10
2 5
1 4
5 6
3 7
5 3
7 1
6 2
4 6
4 3
7 6
stdout
copy 
0.617027
https://ideone.com/xBXveK
mst
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!