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 }

 

上一篇:[BZOJ1821][JSOI2010]部落划分


下一篇:[BZOJ1491]社交网络