[Gauss]HDOJ3976 Electric resistance

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

重点在于转化成考虑电流

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

　　　　　　　U = IR

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

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

　　　　　　　 $U_0$ = 0;

 1 double a[300][300];  // 增广矩阵
 2 double x[300];  // 解
 3 int free_x[300]; // 标记是否为自由未知量
 4 
 5 void Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列
 6 {
 7     //转换为阶梯形式
 8     int col=0, k;
 9     for(k=0;k<n && col<m;k++, col++)
10     {//枚举行
11         int max_r=k;
12         for(int i=k+1;i<n;i++)//找到第col列元素绝对值最大的那行与第k行交换
13             if(fabs(a[i][col])>fabs(a[max_r][col]))
14                 max_r=i;
15         if(fabs(a[max_r][col])<eps)
16             return ;
17         if(max_r!=k)// 与第k行交换
18         {
19             for(int j=col;j<m;j++)
20                 swap(a[k][j], a[max_r][j]);
21             swap(x[k], x[max_r]);
22         }
23         x[k]/=a[k][col];
24         for(int i=col+1;i<m;i++)
25             a[k][i]/=a[k][col];
26         a[k][col]=1;
27         for(int i=0;i<m;i++)
28             if(i!=k)
29             {
30                 x[i]-=x[k]*a[i][k];
31                 for(int j=col+1;j<m;j++)
32                     a[i][j]-=a[k][j]*a[i][col];
33                 a[i][col]=0;
34             }
35     }
36 }
37 
38 void init()
39 {
40     memset(a, 0, sizeof(a));
41     memset(x, 0, sizeof(x));
42 }
43 
44 int main()
45 {
46     int T, ca=1;
47     scanf("%d", &T);
48     while(T--)
49     {
50         int n, m;
51         scanf("%d%d", &n, &m);
52         init();
53         for(int i=0;i<m;i++)
54         {
55             int X, Y, Z;
56             scanf("%d%d%d", &X, &Y, &Z);
57             X--, Y--;
58             a[X][Y]+=1.0/Z;
59             a[Y][X]+=1.0/Z;
60             a[X][X]-=1.0/Z;
61             a[Y][Y]-=1.0/Z;
62         }
63         printf("Case #%d: ", ca++);
64         fill(a[n-1], a[n-1]+n, 0);
65         a[n-1][0]=1;
66         x[0]=1;
67         Gauss(n, n);
68         printf("%.2lf
", x[n-1]);
69     }
70     return 0;
71 }

HDOJ 3976