bzoj 2419 poj 3532 电阻 题解

题解"/>

bzoj 2419 poj 3532 电阻 题解

【原题】

Description

你突破了无数艰难险阻，终于解决了上面那道题，众神犇瞬间就
震惊了。他们发现居然有人可以把那种非人类做的题目做出来。
他们一致同意，最后这道题不能再出数学题了。考虑到两位小盆
友的状态，他们决定考考你的初中物理水平。 
一个电路板，有 N 个接点，M 个电阻。电阻两端都在接点上，
都告诉了你阻值。询问1 号点与N 号点的等效电阻是多少。 
两位小盆友很聪明，他们拿出了一个欧姆表，瞬间就虐爆了…不
过你也不甘落后，你肯定不会用这种投机取巧、误差巨大的方法，
于是你看向了你的电脑。

Input

多组数据，输入直到文件结束 
每组数据第一行两个整数N，M 
接下来 M 行，每行三个非负整数 X，Y，R，表示电阻连接的两
接点和阻值。

Output

每组数据输出一行，一个实数，四舍五入到小数点后两位 
 

Sample Input

Sample Output

【分析】首先必须了解一下基尔霍夫定律（感觉很玄乎，但其实很好懂的）。------>传送门

这里要用到的内容就是：任何一个点（除起点和终点）发出的电流和与接收的电流和相等。即ΣAi=0.

但是这里有很多未知数，怎么办？我不禁想到了高斯消元解方程。设每个点的电势是ai，那么对于点i，我们得到的方程就是：但是起点和终点是不计在内的。因为只是求等效电阻，我们可以自己设a1（起点）和an（终点）的电势的值。为了方便，不妨设起点的电势值为INF，终点的电势值为0，然后对于剩下的n-2个点分别列n-2的方程，再用高斯消元求解。全部解出之后，再根据基尔霍夫定律——电路中的电流等于终点流入的电流（你也可以算起点流出的电流），求出电路中的电流。最后的等效电阻就是起点和终点的电势差除以总电流。

【教训及感想】这道题我一直WA，于是来写一下做题经过，防止下次再犯同样的错误。

①匆匆写完程序。因为还夹带高斯消元，何况没看题解，心中有点惴惴不安。过了样例后果然WA了。

②怎么办呢？我开始手画小的数据，然后人工检验（毕竟样例像什么一样~~~），结果还是过了。

③我把山哥（你不知道山哥？去百度上打“奶牛异或”，第一个就是。看看相关搜索，你会有惊喜）在POJ上已过的程序拿来对拍。辛辛苦苦造好数据。

④发现当n<=10的时候都是无压力的，n>=12开始就会有1.#J这种东西（肯定是除以0了）。于是我把所有可能出现0的地方都特判了——还是照样挂。

⑤仔细一想，精度被卡了？于是我全开成long double，稍微好了一点。

⑤怎么办呢？？？通过研究，我发现我的高斯消元的版本不对，会失精度的。（囧）于是迅速改了一下，改成山哥的版本。但是n变大的时候还是挂了。

⑥可是还是挂，上网查题解，原来数据是根据float造的，要全改float。

⑦还是挂。最后我在后面加了个eps，终于过了。艰辛。

【代码】

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 1000.0
#define V 105
using namespace std;
int num[V][V],n,N,m,i,x,y,j,p,k,zz;
double R[V][V],map[V][V][V],ans[V],s[V],f[V][V],max,z,A,Max,temp;
int main()
{freopen("3532.in","r",stdin);freopen("3532.out","w",stdout);while (scanf("%d%d",&n,&m)!=EOF){memset(R,0,sizeof(R));memset(s,0,sizeof(s));memset(ans,0,sizeof(ans));memset(num,0,sizeof(num));memset(map,0,sizeof(map));memset(f,0,sizeof(f));A=0;for (i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&zz),z=(double)zz,x--,y--,map[x][y][++num[x][y]]=z,map[y][x][++num[y][x]]=z;for (i=0;i<n;i++)for (j=0;j<n;j++)if (num[i][j]){for (k=1;k<=num[i][j];k++)R[i][j]+=(double)1.0/map[i][j][k];R[i][j]=1.0/R[i][j];}ans[0]=INF;ans[n-1]=0;N=n-2;for (i=1;i<=N;i++){if (R[i][0]) f[i][i]-=1.0/R[i][0],s[i]-=ans[0]/R[i][0];if (R[i][n-1]) f[i][i]-=1.0/R[i][n-1];for (j=1;j<=N;j++)if (R[i][j]&&i!=j) f[i][j]=1.0/R[i][j],f[i][i]-=1.0/R[i][j];}for (i=1;i<N;i++)  {  /*for (j=i+1;j<=N;j++)  {  temp=f[j][i];  for (k=i;k<=N;k++)  f[j][k]=f[i][k]*temp-f[j][k]*f[i][i];  s[j]=s[i]*temp-s[j]*f[i][i];  }  */for (j=i+1;j<=N;j++)  {  temp=f[j][i]/f[i][i];  for (k=i;k<=N;k++)  f[j][k]-=f[i][k]*temp;  s[j]-=s[i]*temp;  }  } for (i=N;i;i--)  {  for (j=i+1;j<=N;j++)  s[i]-=ans[j]*f[i][j];  ans[i]=s[i]/f[i][i];  }for (i=0;i<=N;i++) if (R[i][n-1]) A+=ans[i]/R[i][n-1];printf("%.2lf\n",(INF/A+1e-4));}return 0;
}