加载中…
个人资料
winedia
winedia
  • 博客等级:
  • 博客积分:0
  • 博客访问:82,447
  • 关注人气:31
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

HDU 5006 - Resistance 物理题 高斯消元

(2014-09-13 22:04:14)
标签:

hdu

高斯消元

分类: HDU
来来来,以此题纪念一下第一场ACM网(keng)络(dui)赛(you)。
就不吐槽p大教学楼和它的道路一样易让人迷路的神奇特点了,在二楼这层楼找机房就花了整整15分钟我也是醉了。
据说这场是clj出的,小强和阿米巴又将省选曾经美(bei)好(shang)的记忆唤起了。好像真的成功坑到了队友的样子,感觉自己萌萌哒[滚。
这道是这场的最后一道,题意非常简单,不过感觉挺不好想的样子。orz队长鱼丸,感觉好像是一下就想到怎么做的,据说因为不会写高斯消元没有写这题[逗我呢~_~
大概就是先把所有相连边电阻是零这些点的搞成连通块,然后把互相并联的电阻为1的边合起来,如果并了x个,那么这段的总电阻就是1/x。然后就是厉害的东西啦。我们假设S点电势为1,T点电势为0,然后根据经过一个点的出电流等于入电流,电流等于电势差除以电阻,可以对每个点a列一个方程:  ∑(Ua-Ub)/Rab = 0,其中b是与a相邻的节点。这样可以算出每个点的电势。求出了每个点的电势以后就可以求出每个S的出边上的电流了,就是电势差除以那条边的电阻。这样总电流就能知道了,总电流知道以后总电阻就知道了。[这个到底是怎么想出来的啊(´Д` )
由于我卓越的yy能力[滚,我还是成功地在不摸算法一年多以后成功拼凑了一个高斯消元,感觉写法非常不靠谱。不过还是过了。而且运行时间也挺少哒。
HDU <wbr>5006 <wbr>- <wbr>Resistance <wbr>物理题 <wbr>高斯消元
[窝真的不想再用mac调程序了啊啊啊啊,简直高冷得太可怕了这系统,效率至少降低了一大半◡ ヽ(`Д´)ノ ┻━┻ 

#include
#include
#include
using namespace std;
#define N 500
int n,m,C,cnt;
int vis[N],q[N],ed[100010][2],p[N][N];
double A[N][N];
int br[10010],fa[10010];
void clear(){
memset(fa,0,sizeof fa);
memset(vis,0,sizeof vis);
memset(A,0,sizeof A);
memset(p,0,sizeof p);
for (int i = 1;i <= n;i ++) fa[i] = i;
C = 0;
cnt = 0;
}
int find(int x){return fa[x] == x ? x : (fa[x] = find(fa[x]));}
void merge(int u,int v){
int U = find(u);
int V = find(v);
if (U == V) return;
fa[U] = V;
}
void gauss(int n){
for (int i = 1;i <= n;i ++){
double tmp = A[i][i];
for (int j = i + 1;j <= n;j ++) if (A[j][i] < -1e-8 || A[j][i] > 1e-8){
double t = tmp / A[j][i];
for (int k = i;k <= n + 1;k ++){
A[j][k] = A[j][k] * t - A[i][k];
}
}
}
for (int i = n;i;i --){
if (A[i][i]<1e-8 && A[i][i] >-1e-8){
continue;
}
        A[i][n + 1] = A[i][n + 1] / A[i][i];
double tmp = A[i][n + 1];
for (int j = i - 1;j;j --){
A[j][n + 1] -= A[j][i] * tmp;
A[j][i] = 0.0;
}
}
}
void bfs(int x){
int head = 0,tail = 0,now;
q[++ tail] = x;
vis[x] = 1;
memset(vis,0,sizeof vis);
while (head < tail){
now = q[++ head];
for (int i = 1;i <= C;i ++) if (!vis[i] && p[now][i]) q[++ tail] = i,vis[i] = 1;
}
}
int main(){
int T;
int u,v,c,s,t;
scanf("%d",&T);
//cout << T << endl;
while (T --){
scanf("%d%d",&n,&m);
scanf("%d%d",&s,&t);
clear();
for (int i = 1;i <= m;i ++) {
scanf("%d%d%d",&u,&v,&c);
if (c) ed[cnt][0] = u,ed[cnt ++][1] = v;
else merge(u,v);
}
int a;
for (int i = 1;i <= n;i ++) {
a = find(i);
if (a == i) br[a] = ++ C;
}
if (fa[s] == fa[t]) {cout << "0.000000" << endl;continue;}
for (int i = 1;i <= cnt;i ++) {
u = ed[i][0],v = ed[i][1];
if (fa[u] != fa[v]) p[br[fa[u]]][br[fa[v]]] ++,p[br[fa[v]]][br[fa[u]]] ++;
}
bfs(br[fa[s]]);
if (!vis[br[fa[t]]]) {
printf("inf\n");
continue;
}
for (int i = 1;i <= C;i ++) {
if (i == br[fa[s]]) {A[i][i] = 1,A[i][C + 1] = 1.0;continue;}
if (i == br[fa[t]]) {A[i][i] = 1,A[i][C + 1] = 0.0;continue;}
for (int j = 1;j <= C;j ++) if (p[i][j] > 0) A[i][j] -= p[i][j],A[i][i] += p[i][j];
}
gauss(C);
int S = br[fa[s]];
double sumi = 0.0;
for (int i = 1;i <= C;i ++)if (p[S][i]) sumi += (1.0 - A[i][C + 1]) * p[S][i];
printf("%.6lf\n",1.0 / sumi);
}
return 0;
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有