当前位置:编程学习 > C/C++ >>

求一般电路的两点间电阻——高斯消元法

题目描述:
以带权图的形式给出一个用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;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,