Description

Now give you a circuit who has n nodes (marked from 1 to n) , please tell abcdxyzk the equivalent resistance of the circuit between node 1 and node n. You may assume that the circuit is connected. The equivalent resistance of the circuit between 1 and n is that, if you only consider node 1 as positive pole and node n as cathode , all the circuit could be regard as one resistance . (It‘s important to analyse complicated circuit ) At most one resistance will between any two nodes. 

 

Input

In the first line has one integer T indicates the number of test cases. (T <= 100) 

Each test first line contain two number n m(1<n<=50,0<m<=2000), n is the number of nodes, m is the number of resistances.Then follow m lines ,each line contains three integers a b c, which means there is one resistance between node a and node b whose resistance is c. (1 <= a,b<= n, 1<=c<=10^4) You may assume that any two nodes are connected!

 

Output

for each test output one line, print "Case #idx: " first where idx is the case number start from 1, the the equivalent resistance of the circuit between 1 and n. Please output the answer for 2 digital after the decimal point .

 

Sample Input

 1 4 5 1 2 1 2 4 4 1 3 8 3 4 19 2 3 12 

 

Sample Output

 Case #1: 4.21 

给出n个节点，和每个节点中的电阻，问总的电阻是多少。

设每个节点的电势为ui那么总的电压为un - u1 ， 设流过这个电路的电流为1，那么电阻也就是un - u1了。通过每个节点流入的电流和流出的电流相同，得到n个方程。

设在1节点流入的是-1，n节点流出的是1，那么对于u到v有电阻w，也就是u点的电流 (v-u)/w，对于v点的电流为（u-v）/w ;

得到n个方程后高斯消元，设1节点的电势为0，这样就能直接求出n节点的电势，也就是整个的电阻了。

#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std ;#define eps 1e-8double Map[60][60] , a[60] , x[60] ;void swap1(int p,int q,int n){    int i ;    double temp ;    temp = a[p] ; a[p] = a[q] ; a[q] = temp ;    for(i = 1;  i <= n ; i++)    {        temp = Map[p][i] ; Map[p][i] = Map[q][i] ; Map[q][i] = temp ;    }    return ;}double gauss(int n){    int i , j , k , t , max1 ;    double temp ;    for(i = 1 , t = 1 ; i <= n && t <= n ; i++ , t++)    {        max1 = i ;        for(j = i ; j <= n ; j++)            if( fabs(Map[j][t])-fabs(Map[max1][t]) > 0 )            {                max1 = j ;            }        if( fabs(Map[max1][t]) < eps )        {            i-- ;            continue ;        }        if( i != max1 )            swap1(i,max1,n) ;        for(j = i+1 ; j <= n ; j++)        {            if( fabs(Map[j][t]) < eps ) continue ;            temp = Map[j][t] / Map[i][t] ;            a[j] -= (a[i]*temp) ;            for(k = t ; k <= n ; k++)                Map[j][k] -= (Map[i][k]*temp) ;        }    }    for(i = n ; i >= 1 ; i--)    {        x[i] = a[i] ;        for(j = i+1 ; j <= n ; j++)            x[i] -= ( Map[i][j]*x[j] ) ;        x[i] /= Map[i][i] ;    }    return fabs(a[n-1]/Map[n-1][n]) ;}int main(){    int t , tt , n , m , u , v ;    double w ;    scanf("%d", &t) ;    for(tt = 1 ; tt <= t ; tt++)    {        memset(Map,0,sizeof(Map)) ;        memset(a,0,sizeof(a)) ;        scanf("%d %d", &n, &m) ;        a[1] = -1.0 ;        a[n] = 1.0 ;        while(m--)        {            scanf("%d %d %lf", &u, &v, &w) ;            Map[u][u] -= 1.0/w ;            Map[u][v] += 1.0/w ;            Map[v][u] += 1.0/w ;            Map[v][v] -= 1.0/w ;        }        for(int i = 1 ; i <= n ; i++)            Map[i][1] = 0 ;        printf("Case #%d: %.2lf\n", tt, gauss(n) );    }    return 0;}

hdu3976--Electric resistance(高斯消元问题7)