注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2419]电阻  

2015-01-05 20:16:45|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2419: 电阻

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 141  Solved: 57
[Submit][Status]

Description

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

Input

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

Output

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

Sample Input

2 1
1 2 1

Sample Output

1.00

Solution

定义φ(n)=0,I总=1A,则φ(1)就是答案。

基尔霍夫电流定律:对于每个节点,流入总电流=流出总电流

即对于i号点,有Σ I(ij) = 0 ,-> Σ (φ(i)-φ(j))/R(ij) = 0

这样就有n-2个方程组了(1号点与n号点除外),还有两个是

Σ I(1i) = 1  和  φ(n)=0

然后就是高斯消元了

Code

/**************************************************************
    Problem: 2419
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:108 ms
    Memory:996 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 110
int n,m,x,y,v,i,j,k,l;
double f[N][N],tmp,dd[N][N];
double abs(double x){return x>0?x:-x;}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(dd,0,sizeof(dd));
        memset(f,0,sizeof(f));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&v);
            dd[x][y]+=1.0/v;
            dd[y][x]+=1.0/v;
        }
        f[1][n+1]=-1,f[n][n]=1;f[n][n+1]=1;
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            f[i][i]-=dd[i][j];
            f[i][j]+=dd[i][j];
        }
        /*Gauss*/
        for(i=1;i<=n;i++)
        {
            for(l=i,j=i+1;j<=n;j++)
            if(abs(f[j][i])>abs(f[l][i]))l=j;
            if(l!=i)
            {
                for(j=i;j<=n+1;j++)
                tmp=f[l][j],f[l][j]=f[i][j],f[i][j]=tmp;
            }
            for(j=i+1;j<=n;j++)if(abs(f[j][i])>=1e-100)
            for(tmp=f[j][i]/f[i][i],k=i;k<=n+1;k++)
            f[j][k]-=tmp*f[i][k];
        }
        for(i=n;i;i--)
        {
            if(abs(f[i][i])>=1e-100)f[i][n+1]/=f[i][i],f[i][i]=1;
            for(j=i-1;j;j--)f[j][n+1]-=f[j][i]*f[i][n+1],f[j][i]=0;
        }
        printf("%.2lf\n",f[1][n+1]);
    }
}
  评论这张
 
阅读(43)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018