题目链接
类似的题目：Uva 10808
题意：有一个电路，用0/1的电阻连接起来。给定两点，问之间的电阻为多少？
先回忆一下中学物理知识，若用并联串联去做，碰到复杂电路根本分析不清。这里用到基尔霍夫定理。
在任一瞬时，流向某一结点的电流之和恒等于由该结点流出的电流之和。
在任一瞬间，沿电路中的任一回路绕行一周，在该回路上电动势之和恒等于各电阻上的电压降之和。
那么我们对于图中的点（电阻为0的看作一个点，缩点）都可以列方程∑(Ua-Ub)/Rab =0 Rab都是1所以某条边的电流就等于电压差了。
为了方便求结果，我们设S出来的电流是1.0，那么进去T的电流就是1.0， 再随意设一个点的电势为0，那么就可以求出每个点的电势了，那么最后S到T的电压就是电势差，电阻就是电势差 / 1.0 . 上面对于每个点都有一个方程，所以我们能用高斯消元搞一下。
本题的一个亮点就是缩点的操作使用并查集而不是dfs搜索。并且在缩点过程中的标号也非常好。
数据结构 parent，id，idx
1. 先将电阻为0的点都并到一起。
2. 判断S,T是否在一个中，若在则ans=0
3. 循环N个点，将parent仍然为之前值的点当作一个缩点。然后再循环一边，该点的缩点号就是其parent[x]的缩点号
4. 重新并，将所有点连接起来，若此时S,T不通则inf
5.高斯消元构造，这个是难点（对于第一次接触高斯消元的人来说）
高斯消元：
基本将线代中的求阶梯矩阵的方法用程序实现。
1. i表示每一列，在循环过程中找到i列最大的行，与i行对换。
2. 将i行的全部元素都除以A[i][i]，即将第i列的这个元素归一化。
3. 从0行开始，消去i列的这个元素，构建行阶梯形。for(j=0;j<=n;j++) A[k][j]-=f*A[i][j]; //
4. 循环上述步骤直到i->n
还有一个难以理解的就是
A[S][idx]=1;A[T][idx]=-1;A[idx-1][S]++;对于每次询问的两点间等效电阻，先判断说两点是否联通，不连通的话绝逼是1/0（无穷大）。联通的话，将同一个联通分量上的节点都扣出来，假设电势作为变元，然后根据基尔霍夫定律列出方程，因为对于每个节点的电流向量为0，所以每个节点都有一个方程，所有与该节点直接连接的都会有电流流入，并且最后总和为0，（除了a，b两点，一个为1，一个为-1）。用高斯消元处理，但是这样列出的方程组不能准确求出节点的电势，，只能求出各个节点之间电势的关系。所以我们将a点的电势置为0，那么用求出的b点电势减去0就是两点间的电压，又因为电流设为1，所以等效电阻就是电压除以电流。
这样可以理解idx这个位置是电势为0的位置，S是高点势电流1，T是低电势流向idx就是-1，idx-1相当于电源
#include <stdio.h>#include <string.h>#include <math.h>#include <bitset>#include <iostream>#include <algorithm> #define inf 0x3fffffffconst int maxn=10100;typedef unsigned __int64 ull;using namespace std;int parent[maxn],id[maxn];int idx;int U[4*maxn],V[4*maxn],C[4*maxn];int N,M,S,T;double eps=1e-8;double A[500][500];int find(int x){if(parent[x]==x)return x;return parent[x]=find(parent[x]);}void init(){for(int i=0;i<=N;i++)parent[i]=i;idx=0;}void gauss(int n){int i,j,k,r;for(i=0;i<n;i++){r=i;for(j=i+1;j<=n;j++)if(fabs(A[j][i])>fabs(A[r][i])) r=i;if(r!=i)for(j=0;j<=n;j++) swap(A[i][j],A[r][j]);for(j=i+1;j<=n;j++) A[i][j]/=A[i][i];A[i][i]=1;for(k=0;k<n;k++){if(fabs(A[k][i]) <eps || i==k) continue;double f=A[k][i];for(j=0;j<=n;j++) A[k][j]-=f*A[i][j];}}}int main(){int T;int n,m,cas=1;scanf("%d",&T);while(T–){int i,j,k;int u,v,c;scanf("%d%d%d%d",&N,&M,&S,&T);init();for(i=0;i<M;i++){scanf("%d%d%d",U+i,V+i,C+i);if(C[i]==0)parent[find(V[i])]=find(parent[U[i]]);//缩点}if(find(S)==find(T)){printf("0.000000\n");continue;}for(i=1;i<=N;i++)if(parent[i]==i) id[i]=idx++;for(i=1;i<=N;i++)id[i]=id[find(i)];for(i=0;i<idx;i++) parent[i]=i;for(i=0;i<M;i++) parent[find(U[i])]=find(V[i]);if(find(S)!=find(T)){puts("inf");continue;}memset(A,0,sizeof(A));for(i=0;i<M;i++){if(id[U[i]]==id[V[i]]) continue;u=id[U[i]];v=id[V[i]];A[u][u]++;A[v][v]++;A[u][v]–;A[v][u]–;}S=id[S];T=id[T];A[S][idx]=1;A[T][idx]=-1;A[idx-1][S]++;gauss(idx);printf("%.6lf\n",-A[T][idx] + A[S][idx] +eps);}return 0;}
而更像是听见了天地间冥冥中的呼唤，
