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

柔情只为你懂 2021-09-30 03:38 255阅读 0赞

【题目链接】 [http://poj.org/problem?id=3532][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;
    }

转载于:https://www.cnblogs.com/forever97/p/poj3532.html

[http_poj.org_problem_id_3532]: http://poj.org/problem?id=3532