首页 > 代码库 > 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(高斯消元+基尔霍夫定理)