3 条题解
-
0
#include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;} template<class T>inline void sd(T&x){ char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48; while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} template<class T>inline void we(T x){ if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=105,M=2e4+5; const double eps=1e-9; typedef int arr[N]; typedef double db; struct eg{int nx,to,w;}e[M]; int n,m,Mx;arr dg,fi;db Ans,ans[N],G[N][N]; inline void build(int x){ G[n][n]=1; fp(u,1,n-1){ G[u][u]=dg[u]; go(u) if(e[i].w&x)++G[u][v],++G[u][n+1]; else --G[u][v]; } } inline int cmp(db x){return fabs(x)<eps?0:x<0?-1:1;} inline void Gauss(int n){ db t;int mx; fp(i,1,n){mx=i; fp(j,i,n)if(cmp(G[mx][i]-G[j][i]))mx=j; fp(j,i+1,n)if(cmp(G[j][i])){ t=G[j][i]/G[i][i]; fp(k,i,n+1)G[j][k]-=G[i][k]*t; } } fd(i,n,1){ fp(j,i+1,n)G[i][n+1]-=G[i][j]*ans[j]; ans[i]=G[i][n+1]/G[i][i]; } fp(i,1,n)fp(j,1,n+1)G[i][j]=0; } inline void add(int u,int v,int w){static int ce=0;e[++ce]={fi[u],v,w},fi[u]=ce;} int main(){ #ifndef ONLINE_JUDGE file("s"); #endif sd(n),sd(m);int u,v,w; while(m--){ sd(u),sd(v),sd(w),add(u,v,w),++dg[u]; if(u^v)add(v,u,w),++dg[v];cmax(Mx,w); } for(int i=1;i<=Mx;i<<=1) build(i),Gauss(n),Ans+=ans[1]*i; printf("%.3lf\n",Ans); return 0; } -
0
yaosicheng @ 2022-8-29 9:26:53
#include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;} template<class T>inline void sd(T&x){ char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48; while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} template<class T>inline void we(T x){ if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=105,M=2e4+5; const double eps=1e-9; typedef int arr[N]; typedef double db; struct eg{int nx,to,w;}e[M]; int n,m,Mx;arr dg,fi;db Ans,ans[N],G[N][N]; inline void build(int x){ G[n][n]=1; fp(u,1,n-1){ G[u][u]=dg[u]; go(u) if(e[i].w&x)++G[u][v],++G[u][n+1]; else --G[u][v]; } } inline int cmp(db x){return fabs(x)<eps?0:x<0?-1:1;} inline void Gauss(int n){ db t;int mx; fp(i,1,n){mx=i; fp(j,i,n)if(cmp(G[mx][i]-G[j][i]))mx=j; fp(j,i+1,n)if(cmp(G[j][i])){ t=G[j][i]/G[i][i]; fp(k,i,n+1)G[j][k]-=G[i][k]*t; } } fd(i,n,1){ fp(j,i+1,n)G[i][n+1]-=G[i][j]*ans[j]; ans[i]=G[i][n+1]/G[i][i]; } fp(i,1,n)fp(j,1,n+1)G[i][j]=0; } inline void add(int u,int v,int w){static int ce=0;e[++ce]={fi[u],v,w},fi[u]=ce;} int main(){ #ifndef ONLINE_JUDGE file("s"); #endif sd(n),sd(m);int u,v,w; while(m--){ sd(u),sd(v),sd(w),add(u,v,w),++dg[u]; if(u^v)add(v,u,w),++dg[v];cmax(Mx,w); } for(int i=1;i<=Mx;i<<=1) build(i),Gauss(n),Ans+=ans[1]*i; printf("%.3lf\n",Ans); return 0; } -
-1
#include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;} template<class T>inline void sd(T&x){ char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48; while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} template<class T>inline void we(T x){ if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=105,M=2e4+5; const double eps=1e-9; typedef int arr[N]; typedef double db; struct eg{int nx,to,w;}e[M]; int n,m,Mx;arr dg,fi;db Ans,ans[N],G[N][N]; inline void build(int x){ G[n][n]=1; fp(u,1,n-1){ G[u][u]=dg[u]; go(u) if(e[i].w&x)++G[u][v],++G[u][n+1]; else --G[u][v]; } } inline int cmp(db x){return fabs(x)<eps?0:x<0?-1:1;} inline void Gauss(int n){ db t;int mx; fp(i,1,n){mx=i; fp(j,i,n)if(cmp(G[mx][i]-G[j][i]))mx=j; fp(j,i+1,n)if(cmp(G[j][i])){ t=G[j][i]/G[i][i]; fp(k,i,n+1)G[j][k]-=G[i][k]*t; } } fd(i,n,1){ fp(j,i+1,n)G[i][n+1]-=G[i][j]*ans[j]; ans[i]=G[i][n+1]/G[i][i]; } fp(i,1,n)fp(j,1,n+1)G[i][j]=0; } inline void add(int u,int v,int w){static int ce=0;e[++ce]={fi[u],v,w},fi[u]=ce;} int main(){ #ifndef ONLINE_JUDGE file("s"); #endif sd(n),sd(m);int u,v,w; while(m--){ sd(u),sd(v),sd(w),add(u,v,w),++dg[u]; if(u^v)add(v,u,w),++dg[v];cmax(Mx,w); } for(int i=1;i<=Mx;i<<=1) build(i),Gauss(n),Ans+=ans[1]*i; printf("%.3lf\n",Ans); return 0; }
- 1
