记录编号	85023	评测结果	AAAAAAAAAA
题目名称	电阻问题	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.076 s
提交时间	2013-12-23 21:24:27	内存使用	1.03 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
const int SIZEN=210;
int N,M;
bool cn[SIZEN][SIZEN]={0};//边之间是否有导线
double sr[SIZEN][SIZEN]={0};//边之间的等效电阻
double coeff_data[SIZEN][SIZEN]={0},const_data[SIZEN]={0};//描述一个方程,系数和常数
double e[SIZEN]={0};//方程的解,即每个点的电势
void Gauss_Jordan_Elim(double *A[],double b[],int n,int m,double x[]){//方程由二维数组A和一维数组B描述,n行m列(下标从1),解存放在数组x中
	//这里不进行列交换,只进行行交换,因此要求一定能得出结果(即m=n),但保留m接口以便将来修改
	double eps=1e-10;
	int i,j,k;
	double temp;
	for(j=1;j<=n;j++){//n个方程可消去n个元素
		k=0;
		for(i=j;i<=n;i++){
			if(fabs(A[i][j])<eps) continue;
			if(!k||fabs(A[i][j])>fabs(A[k][j])) k=i;
		}
		if(!k) continue;
		swap(A[j],A[k]);swap(b[j],b[k]);
		for(i=1;i<=n;i++){
			if(i==j) continue;
			temp=A[i][j]/A[j][j];
			for(k=1;k<=m;k++) A[i][k]-=A[j][k]*temp;
			b[i]-=b[j]*temp;
		}
	}
	//令其余变量均为0,此时矩阵对角化,方程均为"kx=b"形式
	for(i=1;i<=n;i++) x[i]=b[i]/A[i][i];
	for(i=n+1;i<=m;i++) x[i]=0.0;
}
void work(void){
	e[1]=1,e[N]=0;
	double *p[SIZEN];
	int i;
	for(i=2;i<N;i++) p[i-1]=&coeff_data[i][1];//只有从下标为2的列开始的矩阵才有价值
	//这种做法不推荐使用,过于危险,容易导致溢出
	Gauss_Jordan_Elim(p,const_data+1,N-2,N-2,e+1);
	double totcr=0;//总电流
	for(i=2;i<=N;i++){
		if(!cn[1][i]) continue;
		totcr+=(1.0-e[i])/sr[1][i];
	}
	double ans=1.0/totcr;
	printf("%.2lf\n",ans);
}
void init(void){
	scanf("%d%d",&N,&M);
	int i,j,u,v;
	double w;
	for(i=1;i<=M;i++){
		scanf("%d%d%lf",&u,&v,&w);
		if(u==v) continue;
		if(!cn[u][v]) cn[u][v]=cn[v][u]=true,sr[u][v]=sr[v][u]=w;
		else sr[u][v]=sr[v][u]=1.0/(1.0/w+1.0/sr[u][v]);
		//这里得出了每两个相邻节点之间的电阻值
	}
	double tot,temp;
	for(i=2;i<N;i++){//对第i个节点列方程,储存在coeff_data[i]和const_data[i]中
		tot=0;
		for(j=1;j<=N;j++){
			if(!cn[i][j]) continue;
			temp=1.0/sr[i][j];
			tot+=temp;
			coeff_data[i][j]=temp;
		}
		coeff_data[i][i]=-tot;
	}
	//至此得到了N-2个左端为一些未知数,右端为0的方程
	//下面规定节点1的电势为1,节点N的电势为0并相应修改方程
	for(i=2;i<N;i++){
		const_data[i]-=coeff_data[i][1];
		coeff_data[i][1]=0;
		coeff_data[i][N]=0;
	}
}
int main(){
	freopen("resistor.in","r",stdin);
	freopen("resistor.out","w",stdout);
	init();
	work();
	return 0;
}