Description 给出一个电路图，无重边，边权为电阻大小，求1～n的等效电阻 Input 第一行一整数T表示用例组数，每组用例第一行为两整数n和m分别表示点数和边数，之后m行每行三个整数u,v,w表示u和v之间边权为w Output 对于每组用例，输出1~n之间的等效电阻，结果保留两位小数 Sample Input 1 4 5 1 2 1 2 4 4 1 3 8 3 4 19 2 3 12 Sample Output Case #1: 4.21 Solution 根据n个点的流入电流等于流出电流可以列出n个方程，可以假设1这个点流入电流为-1, 这样设点电势为0，那么可以知道n点的电势就等于等效电阻了，流入肯定等于流出的，上面列的方程组中第n个的是多余的，可以去掉，替换成1点电压为0，之后高斯消元求解即可，答案就是n点的电阻x[n-1] Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define eps 1e-9 #define maxn 111 double a[maxn][maxn],x[maxn]; int Gauss(int equ,int var) { 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(int 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 main() { int T,n,m,res=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); int u,v,w; for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); a[u-1][v-1]+=1.0/w; a[u-1][u-1]+=-1.0/w; a[v-1][u-1]+=1.0/w; a[v-1][v-1]+=-1.0/w; } for(int i=0;i<n-1;i++)x[i]=0; x[0]=1; for(int i=0;i<n;i++)a[n-1][i]=0; x[n-1]=0; a[n-1][0]=1; Gauss(n,n); printf("Case #%d: %.2lf\n",res++,x[n-1]); } return 0; }