首页 > 代码库 > HDU5006 Resistance(高斯消元)

HDU5006 Resistance(高斯消元)

2024-07-30 20:08:28   259人阅读

给你一个复杂的网路图，然后告诉你s,t，求s,t的等效电阻。方法是设s的电势为1，t的电势为0.然后对于其它的每个点x,满足的是sigma(ux-uy)/R(x,y)（即对每个与x相连的节点y,电势差除以电阻的和为0，应该是基尔霍夫定律什么的），然后就列出来了一堆方程，解出每个点的电势，对于源点连出去的所有边，求一下电流，知道总电流，而且也知道总电势，就可以知道电阻了。

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cmath>#include <queue>#include <cassert>#include <vector>using namespace std;#define maxn 11000#define eps 1e-7struct Edge{    int u,v,c;    Edge(int ui,int vi,int ci):u(ui),v(vi),c(ci){}    Edge(){}};int dcmp(double x){    return (x>eps)-(x<-eps);}vector<Edge> E;vector<int> G[maxn];int n,m,s,t;int bel[maxn];int btot;void dfs(int u,int mark){    bel[u]=mark;    for(int i=0;i<G[u].size();++i){        int v=G[u][i];        if(bel[v]) continue;        else dfs(v,mark);    }}void getBelong(){    btot=0;    memset(bel,0,sizeof(bel));    for(int i=1;i<=n;++i){        if(!bel[i]){            ++btot;            dfs(i,btot);        }    }}int cnt[500][500];double mat[500][500];void gauss(int n){    for(int i=1;i<=n;++i){        int pivot=i;        for(int j=i;j<=n;++j){            if(abs(mat[j][i])>abs(mat[pivot][i])) pivot=j;        }        for(int x=1;x<=n+1;++x){            swap(mat[i][x],mat[pivot][x]);        }        if(abs(mat[i][i])<eps) continue;        for(int j=i+1;j<=n+1;++j){            mat[i][j]/=mat[i][i];        }        for(int j=1;j<=n;++j){            if(i!=j){                for(int k=i+1;k<=n+1;++k){                    mat[j][k]-=mat[j][i]*mat[i][k];                }            }        }    }}int main(){    int T;cin>>T;    while(T--){        scanf("%d%d%d%d",&n,&m,&s,&t);        for(int i=0;i<=n;++i) G[i].clear();        E.clear();        int ui,vi,ci;        for(int i=0;i<m;++i){            scanf("%d%d%d",&ui,&vi,&ci);            if(ci==0){                G[ui].push_back(vi);                G[vi].push_back(ui);            }            else{                E.push_back(Edge(ui,vi,ci));            }        }        getBelong();        if(bel[s]==bel[t]){            printf("%.6lf\n",0);continue;        }        memset(cnt,0,sizeof(cnt));        memset(mat,0,sizeof(mat));        for(int i=0;i<E.size();++i){            ui=E[i].u;vi=E[i].v;            if(bel[ui]!=bel[vi]){                cnt[bel[ui]][bel[vi]]++;                cnt[bel[vi]][bel[ui]]++;            }        }        for(int i=1;i<=btot;++i){            if(i==bel[s]){                mat[i][i]=1.0;                mat[i][btot+1]=1;                continue;            }            else if(i==bel[t]){                mat[i][i]=1.0;                mat[i][btot+1]=0;                continue;            }            for(int j=1;j<=btot;++j){                if(i==j||cnt[i][j]==0) continue;                mat[i][i]+=cnt[i][j];                mat[i][j]-=cnt[i][j];            }        }        gauss(btot);        double I=0;        for(int i=1;i<=btot;++i){            if(i==bel[s]) continue;            if(cnt[bel[s]][i]>0){                I+=(1-mat[i][btot+1])*cnt[bel[s]][i];            }        }        double R=1/I;        if(dcmp(I-eps)==0) {            printf("inf\n");            continue;        }        printf("%.6lf\n",R);    }    return 0;}

 

HDU5006 Resistance(高斯消元)


联系
我们