【bzoj2419】电阻

  • 高斯消元重修系列第二题

引用妹主席的一句话:

如今的OI界啊，仙人掌当道，玄学题横行，物理题为[和谐]一方

这种物理题我也是醉了

首先普及一下电流守恒定律：流入一个点的电流和等于流出这个点的电流和（和网络流有点像）

然后根据欧姆定律有：$I_{i,j}=\frac{E_i-E_j}{R_{i,j}}$

带入电流守恒定律有：$\sum \frac{E_i-E_j}{R_{i,j}}=0$ (i与j有电阻相连)

特别的，对于1号点：$\sum \frac{E_i-E_j}{R_{i,j}}=1$

对于n号点：$\sum \frac{E_i-E_j}{R_{i,j}}=-1$

根据这些列出n个方程，高斯消元即可

注意重边要累加电阻，自环要忽略，上邻接矩阵存图即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
using namespace std;
double a[510][510],Map[510][510];
int n,m;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void init(){
	memset(Map,0,sizeof(Map));
	memset(a,0,sizeof(a));
	for(int i=1;i<=m;++i){
		int x=read(),y=read(),r=read();
		Map[x][y]+=1.0/r;  Map[y][x]+=1.0/r;
	}
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
		a[i][i]+=Map[i][j];  a[i][j]-=Map[i][j];
	}
	a[1][n+1]=1; a[n][n+1]=-1;
}
bool gauss(){
	int now=1;
	for(int i=1,temp;i<=n;++i){
		for(temp=now;temp<=n;++temp) if(fabs(a[temp][i])>eps) break;
		if(temp>n) continue;
		if(temp!=now) for(int j=1;j<=n+1;++j) swap(a[now][j],a[temp][j]);
		double t=a[now][i];
		for(int j=1;j<=n+1;++j) a[now][j]/=t;
		for(int j=1;j<=n;++j)if(j!=now){
			double t=a[j][i];
			for(int k=1;k<=n+1;++k) a[j][k]-=t*a[now][k];
		}
		++now;
	}
	for(int i=now;i<=n;++i)if(fabs(a[i][n+1])>eps)return 0;
	return 1;
}
void output(){
	printf("%.2lf\n",a[1][n+1]);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	while(scanf("%d%d",&n,&m)!=EOF){
		init();gauss();output();
	}
	return 0;
}

本文标题:【bzoj2419】电阻

文章作者:chty

发布时间:2017年03月10日 - 20时56分

最后更新:2018年03月02日 - 17时26分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,