首页 > 代码库 > POJ 3532 Resistance(高斯消元+基尔霍夫定理)
POJ 3532 Resistance(高斯消元+基尔霍夫定理)
【题目链接】 http://poj.org/problem?id=3532
【题目大意】
给出n个点,一些点之间有电阻相连,求1~n的等效电阻
【题解】
有基尔霍夫定理:任何一个点(除起点和终点)发出的电流和与接收的电流和相等。
由ΣAi=0可以得到Σ(Ui-Uj)/Rij=0,Σ(U1-Uj)/R1j=1,Σ(Un-Uj)/Rnj=-1
我们设电流为1A,终点电势为0列关于电势的方程组,最后的等效电阻就是起点和终点的电势差除以总电流
【代码】
#include <cstdio>#include <algorithm>#include <cmath> #include <cstring> using namespace std;const double eps=1e-9;const int MAXN=220;double a[MAXN][MAXN],x[MAXN];// a和x分别为方程的左边的矩阵和等式右边的值,求解之后x存的就是结果int equ,var;// 方程数和未知数个数// 返回0表示无解,1表示有解int Gauss(){ int i,j,k,col,max_r; for(k=0,col=0;k<equ&&col<var;k++,col++){ max_r=k; for(i=k+1;i<equ;i++)if(fabs(a[i][col])>fabs(a[max_r][col]))max_r=i; if(fabs(a[max_r][col])<eps)return 0; if(k!=max_r){ for(j=col;j<var;j++)swap(a[k][j],a[max_r][j]); swap(x[k],x[max_r]); }x[k]/=a[k][col]; for(j=col+1;j<var;j++)a[k][j]/=a[k][col]; a[k][col]=1; for(i=0;i<equ;i++)if(i!=k){ x[i]-=x[k]*a[i][k]; for(j=col+1;j<var;j++)a[i][j]-=a[k][j]*a[i][col]; a[i][col]=0; } } return 1;}int N,M,u,v;double r;void solve(){ memset(a,0,sizeof(a)); for(int i=0;i<M;i++){ scanf("%d%d%lf",&u,&v,&r); --u;--v; double s=1.0/r; a[u][u]+=s; a[v][v]+=s; a[u][v]-=s; a[v][u]-=s; }a[N-1][N-1]+=1; x[0]=1.0; x[N-1]=-1.0; equ=N; var=N; Gauss(); printf("%.2f\n",x[0]);}int main(){ while(~scanf("%d%d",&N,&M))solve(); return 0;}
POJ 3532 Resistance(高斯消元+基尔霍夫定理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。