Electric resistance

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 907    Accepted Submission(s): 521

Problem 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个结点的电路图,任意两个结点均联通,

任意两点之间最多有一个电阻,求结点1与N之间的等效电阻。

 

分析：外加电流源求等效电阻,用结点电压法,以结点1为参考结点U₀=0,

即把结点1作为电势零点,结点2,3,4,...,N的电势为U_n1,U_n2,U_n3,...,U_n(N-1),

一共N-1个未知数,再在结点1与结点N之间加一个电流源I,列结点电压方程,

那么一共可列N-1个独立方程(含N-1个未知数),再用高斯消元解方程(一定有解),

解出U_n(N-1)，等效电阻R=(U_n(N-1)-U₀)/I=U_n(N-1)/I,为方便计算取I=1.0A，

那么R=U_n(N-1).

 

#include
        
         #include
         
          #include
          
           #include
           
            using namespace std;double a[60][60];void Guass(int N,int M){    for(int i=1;i<=N;i++)//i是列数,一个一个消去    {
      //上三角         if(fabs(a[i][i])<1e-6)//第i行第i个为0         {
      //找出i+1到第M行中,第i个数不为0的行             int p=M;            for(;p>i;p--)            if(fabs(a[p][i])>1e-6) break;            if(p==i) continue;            else swap(a[i],a[p]);//交换i,p两行         }        for(int k=i+1;k<=M;k++)        {            for(int j=i+1;j<=N+1;j++)            {                a[k][j]-=a[i][j]/a[i][i]*a[k][i];            }            a[k][i]=0;        }    }    //从下往上消去     for(int i=N;i;i--)//第i个解     {        for(int k=i-1;k;k--)//消去1到i-1行的第i个元素        {            a[k][N+1]-=a[i][N+1]/a[i][i]*a[k][i];            a[k][i]=0;        }    }}int main(){    int T,cas=0;    int N,M;//N个结点M条支路     scanf("%d",&T);    while(T--)    {        memset(a,0,sizeof(a));         scanf("%d%d",&N,&M);        for(int i=0;i