%物理大神
重点是设电势为未知量
#include<cstdio> #include<cstring> #include<iostream> #define maxn 151 using namespace std; int n,m,head[maxn],tot=1; struct edge{int v,next;double w;}e[maxn*maxn*2]; void adde(int a,int b,double c){e[tot].v=b,e[tot].next=head[a],e[tot].w=c;head[a]=tot++;} double a[maxn][maxn]; void solve(){ for(int p,i=1;i<=n;i++){ for(p=i;p<=n;p++)if(a[p][i])break; if(p>n)continue; for(int j=1;j<=n+1;j++)swap(a[i][j],a[p][j]); double z=a[i][i]; for(int j=1;j<=n+1;j++)a[i][j]/=z; for(int j=1;j<=n;j++)if(a[j][i]&&j!=i){ double d=a[j][i]/a[i][i]; for(int k=1;k<=n+1;k++)a[j][k]-=a[i][k]*d; } } } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ tot=1; memset(head,0,sizeof(head)); memset(a,0,sizeof(a)); int x,y;double c; for(int i=1;i<=m;i++){ scanf("%d%d%lf",&x,&y,&c); adde(x,y,c),adde(y,x,c); } for(int i=1;i<n;i++){ for(int j=head[i];j;j=e[j].next){ int v=e[j].v; a[i][v]+=1.0/e[j].w; a[i][i]-=1.0/e[j].w; } }a[1][n+1]=-1; for(int i=1;i<=n+1;i++)a[n][i]=0;a[n][n]=1; solve(); printf("%.2lf\n",a[1][n+1]); } return 0; }
