13 条题解

  • -2
    @ 2022-8-29 9:27:20 
    #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;
}
    • @ 2022-9-22 21:07:56

      别整这么些幺蛾子，自欺欺人，这是很愚蠢的行为。

  • -2
    @ 2022-8-29 9:27:20 
    #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;
}
    • -2
      @ 2022-8-29 9:27:20 
      #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;
}
      • -2
        @ 2022-8-29 9:27:19 
        #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;
}
        • -2
          @ 2022-8-29 9:27:18 
          #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;
}
          • -2
            @ 2022-8-29 9:27:15 
            #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;
}
            • -2
              @ 2022-8-29 9:27:15 
              #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;
}
              • -2
                @ 2022-8-29 9:27:14 
                #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;
}
                • -2
                  @ 2022-8-29 9:27:11 
                  #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;
}
                  • -2
                    @ 2022-8-29 9:27:11 
                    #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;
}
                    • -2
                      @ 2022-8-29 9:27:11 
                      #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;
}
                      • -2
                        @ 2022-8-29 9:27:11 
                        #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;
}
                        • -2
                          @ 2022-8-29 9:27:00 
                          #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

                          [HNOI2011] XOR和路径

                          信息

                          ID
                          2337
                          时间
                          1000ms
                          内存
                          256MiB
                          难度
                          5
                          标签
                          (无)
                          递交数
                          36
                          已通过
                          17
                          上传者
                          1. 关于
                          2. 联系我们
                          3. 隐私
                          4. 服务条款
                          5. 版权申诉
                          6. Language
                          7. 兼容模式
                          8. 主题
                          2. © 2021-2024 Hydro.ac
                          4. Worker 0 in 91ms
                          5. Hydro v4.11.2 Professional