P2973 [USACO10HOL]赶小猪
跟那个某省省选题(具体忘了)游走差不多...
把边搞到点上然后按套路Gauss即可
貌似有人说卡精度，$eps≤1e-13$，然而我$1e-12$也可以过...
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #define writeln(x) write(x),puts("") 6 #define writep(x) write(x),putchar(' ') 7 using namespace std; 8 inline int read(){ 9 int ans=0,f=1;char chr=getchar(); 10 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 11 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 12 return ans*f; 13 }void write(int x){ 14 if(x<0) putchar('-'),x=-x; 15 if(x>9) write(x/10); 16 putchar(x%10+'0'); 17 }const int M = 305; 18 int n,m,p,q,du[M],e[M][M]; 19 double a[M][M],ans[M],b[M]; 20 const double eps=1e-13; 21 inline void Gauss(){ 22 for(int i=1;i<=n;i++){ 23 int maxn=i; 24 for(int j=i+1;j<=n;j++) if(fabs(a[j][i]-a[maxn][i])<eps) maxn=j; 25 for(int j=1;j<=n+1;j++) swap(a[maxn][j],a[i][j]); 26 for(int j=n+1;j>=i;j--) 27 for(int k=i+1;k<=n;k++) 28 a[k][j]-=a[k][i]/a[i][i]*a[i][j]; 29 } 30 for(int i=n;i>=1;i--){ 31 for(int j=i+1;j<=n;j++) 32 a[i][n+1]-=a[j][n+1]*a[i][j]; 33 a[i][n+1]/=a[i][i]; 34 } 35 for(int i=1;i<=n;i++) ans[i]=a[i][n+1]; 36 } 37 int main(){ 38 n=read(),m=read(),p=read(),q=read(); 39 const double ps=p*1.0/q; 40 for(int i=1;i<=m;i++){ 41 int x=read(),y=read(); 42 e[x][y]=e[y][x]=1; 43 du[x]++,du[y]++; 44 } 45 for(int i=1;i<=n;i++){ 46 a[i][i]=1.0; 47 for(int j=1;j<=n;j++) 48 if(e[i][j]) 49 a[i][j]-=(1.0-ps)/du[j]; 50 } 51 a[1][n+1]=1.0; 52 Gauss(); 53 for(int i=1;i<=n;i++)printf("%.9lf\n",ans[i]*ps); 54 return 0; 55 }
