首页 > 代码库 > (高斯消元)HDU 5006 Resistance 2014 鞍山网赛
(高斯消元)HDU 5006 Resistance 2014 鞍山网赛
题目链接
题意:有一个电路,用0/1的电阻连接起来。给定两点,问之间的电阻为多少?
先回忆一下中学物理知识,若用并联串联去做,碰到复杂电路根本分析不清。这里用到基尔霍夫定理。
在任一瞬时,流向某一结点的电流之和恒等于由该结点流出的电流之和。
在任一瞬间,沿电路中的任一回路绕行一周,在该回路上电动势之和恒等于各电阻上的电压降之和。
那么我们对于图中的点(电阻为0的看作一个点,缩点)都可以列方程
为了方便求结果,我们设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
#include <stdio.h> #include <string.h> #include <math.h> #include <bitset> #include <iostream> #include <algorithm> #define inf 0x3fffffff const 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; }
(高斯消元)HDU 5006 Resistance 2014 鞍山网赛