POJ 3532 Resistance（高斯消元+基尔霍夫定理）

【题目大意】

　　给出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;

}

uj

POJ 3532 Resistance（高斯消元+基尔霍夫定理）