hdu3976 Electric resistance
传送门
题意
给出(n(n<=50))个节点,(m(m<=2000))个电阻,两个节点之间最多有一个电阻,计算整个电路的等效电阻。
题解
以每个节点的电压为未知数,根据基尔霍夫电流定律(每个节点的流入电流等于流出电流),为每个节点建立方程。
设节点x和节点y之间有电阻w,那么这条支路上的电流为压降/电阻,也就是(frac{|U_x-U_y|}{w})
节点(x)的电流加上(frac{U_y-U_x}{w}=frac{-1}{w}U_x+frac{1}{w}U_y)
节点(y)的电流加上(frac{U_x-U_y}{w}=frac{1}{w}U_x+frac{-1}{w}U_y)。
所以在节点(x)所对应的方程中,(U_x)的系数加上(frac{-1}{w}),(U_y)的系数加上(frac{1}{w})
同理在节点(y)所对应的方程中,(U_x)的系数加上(frac{1}{w}),(U_y)的系数加上(frac{-1}{w})
整个电路的等效电阻为(frac{U_{n-1}-U_0}{I}),(I)为流入节点(0)(流出节点(n-1))的电流
为了简化计算,设(I=1),这样等效电阻就变成了(U_{n-1}-U_0)
通过高斯消元求解线性方程组,时间复杂度(O(n^3))
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=60;
int T,n,m;
double a[maxn][maxn],ans[maxn];
int gauss(int n,int m){
for(int row=0,col=0;row<n && col<m;row++,col++){
int maxi=row;
for(int i=row+1;i<n;i++){
if(fabs(a[i][col])>fabs(a[m][col])) maxi=i;
}
if(fabs(a[maxi][col])<eps) return 0;
if(row!=maxi){
for(int j=col;j<m;j++) swap(a[row][j],a[maxi][j]);
swap(ans[row],ans[maxi]);
}
ans[row]/=a[row][col];
for(int j=col+1;j<m;j++) a[row][j]/=a[row][col];
a[row][col]=1;
for(int i=0;i<n;i++){
if(i!=row){
ans[i]-=ans[row]*a[i][col];
for(int j=col+1;j<m;j++){
a[i][j]-=a[row][j]*a[i][col];
}
a[i][col]=0;
}
}
}
return 1;
}
int main(void){
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%d %d",&n,&m);
memset(a,0,sizeof(a));
memset(ans,0,sizeof(ans));
while(m--){
int x,y;
double w;
scanf("%d %d %lf",&x,&y,&w);
a[x-1][x-1]-=1.0/w;
a[y-1][y-1]-=1.0/w;
a[x-1][y-1]+=1.0/w;
a[y-1][x-1]+=1.0/w;
}
ans[0]=1;
ans[n-1]=-1;
gauss(n,n);
printf("Case #%d: %.2f
",cas,ans[n-1]-ans[0]);
}
return 0;
}