[Gauss]HDOJ3976 Electric resistance

题意： 一看图就明白了 要求的是1与n端点间的等效电阻

重点在于转化成考虑电流

根据KCL定理：在任一瞬间流出（流入）该节点的所有电流的代数和恒为零

　　　　　　　U = IR

　可以令1点的电势为零 那么n点的电势就等于它的等效电阻

可以列出方程组  $\sum\limits \frac{U_j-U_i}{R_ij} + I = 0$

　　　　　　　  $U_0$ = 0;

 double a[][];  // 增广矩阵
 double x[];  // 解
 int free_x[]; // 标记是否为*未知量

 void Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列
 {
     //转换为阶梯形式
     int col=, k;
     for(k=;k<n && col<m;k++, col++)
     {//枚举行
         int max_r=k;
         for(int i=k+;i<n;i++)//找到第col列元素绝对值最大的那行与第k行交换
             if(fabs(a[i][col])>fabs(a[max_r][col]))
                 max_r=i;
         if(fabs(a[max_r][col])<eps)
             return ;
         if(max_r!=k)// 与第k行交换
         {
             for(int j=col;j<m;j++)
                 swap(a[k][j], a[max_r][j]);
             swap(x[k], x[max_r]);
         }
         x[k]/=a[k][col];
         for(int i=col+;i<m;i++)
             a[k][i]/=a[k][col];
         a[k][col]=;
         for(int i=;i<m;i++)
             if(i!=k)
             {
                 x[i]-=x[k]*a[i][k];
                 for(int j=col+;j<m;j++)
                     a[i][j]-=a[k][j]*a[i][col];
                 a[i][col]=;
             }
     }
 }

 void init()
 {
     memset(a, , sizeof(a));
     memset(x, , sizeof(x));
 }

 int main()
 {
     int T, ca=;
     scanf("%d", &T);
     while(T--)
     {
         int n, m;
         scanf("%d%d", &n, &m);
         init();
         for(int i=;i<m;i++)
         {
             int X, Y, Z;
             scanf("%d%d%d", &X, &Y, &Z);
             X--, Y--;
             a[X][Y]+=1.0/Z;
             a[Y][X]+=1.0/Z;
             a[X][X]-=1.0/Z;
             a[Y][Y]-=1.0/Z;
         }
         printf("Case #%d: ", ca++);
         fill(a[n-], a[n-]+n, );
         a[n-][]=;
         x[]=;
         Gauss(n, n);
         printf("%.2lf\n", x[n-]);
     }
     return ;
 }

HDOJ 3976