題目描述： 以帶權圖的形式給出一個用n個結點和m個電阻連接的電路，求點1與點n兩點間的電阻。 問題分析： 省隊集訓居然會出這種學霸題——太坑爹了啊= =！考的時候完全不會。 解法基於兩個事實： 1.<基爾霍夫定律>：所有點的電流總流入等於總流出（除了1和n兩點）。 2.<歐姆定律>：I=U/R=(Ex-Ey)/R 因為電流方向不好確定，不妨令電流可正可負，那麼定律1可以表示成“總流出之和等於0”，於是對每個節點列一方程，高斯消元解之即可。 有幾個值得注意的地方： 1.自環直接無視，重邊用倒數和公式合成一條。 2.高斯消元每次找系數絕對值最大的一項，使除法得到的比值盡可能小。這樣可以保證解出方程組，也能得到很高的精度。（浮點數貌似越小精度越高 （具體實現看代碼） Code： [cpp] #include<cstdio> #include<cstring> using namespace std; #define abs(_) ({ double __=_; (__>0)?__:-__; }) int n,m,u,v,w,a[200][200]; double b[200][200]; double now,tot,gs[200][200],e[200],ans=0; void gauss() { int c,t,i,j; double k,tmp; for(c=1; c<=n; c++) { t=c; for(i=c+1; i<=n; i++) if( abs(gs[i][c]) > abs(gs[t][c]) ) t=i; for(j=0; j<=n; j++) tmp=gs[c][j], gs[c][j]=gs[t][j], gs[t][j]=tmp; for(i=c+1; i<=n; i++) { k=gs[i][c]/gs[c][c]; for(j=0; j<=n; j++) gs[i][j] -= gs[c][j]*k; } } for(c=n; c>=1; c--) { tmp=gs[c][0]; for(j=c+1; j<=n; j++) tmp-=gs[c][j]*e[j]; e[c]=tmp/gs[c][c]; } } int main() { int i,j; freopen("resistor.in" , "r", stdin); freopen("resistor.out", "w", stdout); for(;;) { if( scanf("%d%d", &n, &m) == -1) break; memset(gs,0,sizeof(gs)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(e,0,sizeof(e)); for(i=1; i<=m; i++) { scanf("%d%d%d", &u, &v, &w); if(u==v) continue; if(!a[u][v]) a[u][v]=a[v][u]=1, b[u][v]=b[v][u]=w; else b[u][v]= 1.0/(1.0/w + 1.0/b[u][v]), b[v][u]=b[u][v]; } for(i=2; i<n; i++) { tot=0; for(j=1; j<=n; j++) if(a[i][j]) { now=1.0/b[i][j]; gs[i][j]=now, tot-=now; } gs[i][i]=tot; } gs[1][0]=1, gs[1][1]=1; gs[n][0]=0, gs[n][n]=1; gauss(); ans = 0; for(j=1; j<=n; j++) if(a[1][j]) ans += (1-e[j])/b[1][j]; printf("%.2lf\n", (double)1.0/ans); } return 0; }
