自动搬运

查看原文

来自洛谷，原作者为

	Krimson 别祈祷

搬运于2025-08-24 22:05:32，当前版本为作者最后更新于2020-10-21 13:09:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置芝士：

1. 初中物理（大概初一初二水平？）

2. 图论（会建图就行）

3. dfs

此处先以样例三为例

在读入数据之后很轻松就能建出一个这样的图，其中16是起点，1是终点
但是电流是带有方向的，而上面这个图由于是无向边，不能很好地模拟电流

于是考虑把上面的图转换成有向图

这样子就方便多了，只要遍历一遍图就可以求出总电阻了（电阻公式不用我多说了吧）
根据串连电路的性质，最大电流肯定就是总电压除以总电阻
而最小电流则肯定出现在某条并联电路的支路上面
这里以上图中15->11这一段电路为例，设这一段的电阻为$R_\texttt{并}$
于是求其中任意一段的电流就是$\frac {\frac {R_\texttt{总}}{R_\texttt{并}}*U}{R}$
剩下的就是代码实现了

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define ll long long
const int MAXN=2e4+7,MAXM=5e4+7;
il ll read(){
    bool f=true;ll x=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=false;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(f) return x;
    return ~(--x);
}
il void write(const ll &x){if(x>9) write(x/10);putchar(x%10+'0');}
vector<int> g[MAXN],vv[MAXN],to[MAXN],v[MAXN];//g,vv是一开始的无向边;to,v是后来的有向边
int n,m,be,ed;
ll power;//总电压
int mark[MAXN];//标记是否到达过
int cnt[MAXN],Cnt[MAXN];//用来建图的，可以理解为第一个是度，第二个是入度
//这三个用来记录并联电路的位置，电阻大小以及最大支路电阻
vector<int> bp;
vector<double> va;
vector<ll> maxs; 
bool flag=true;//建图时使用
bool fl[MAXN];//标记是否是并联电路
ll get(ll x,ll y){return x/(__gcd(x,y))*y;}
void dfs1(int now){
    if(now==ed) return;
    if(cnt[now]==1){//如果当前结点位置是一个串连电路
        mark[now]=1;
        for(ri i=0;i<g[now].size();++i){
            int x=g[now][i];
            if(mark[x]) continue;
            --cnt[x];
            ++Cnt[x];
            to[now].push_back(x),v[now].push_back(vv[now][i]);
            dfs1(x);
        }
    }
    else if(flag){//如果不是串连电路，且flag为真，那么就说明这个点是并联电路的起点
    //具体实现还是看代码吧
        fl[now]=true;
        bp.push_back(now);
        flag=false;
        mark[now]=1;
        for(ri i=0;i<g[now].size();++i){
            int x=g[now][i];
            if(mark[x]) continue;
            to[now].push_back(x),v[now].push_back(vv[now][i]);
            if(cnt[now]--==1){
                flag=true;
            }
            --cnt[x];
            ++Cnt[x];
            dfs1(x);
        }
    }
}
double ans=0;//总电阻
void get_ans(int rot){//用来求总电阻的
    while(rot!=ed){//如果进入了并联电路
        if(fl[rot]){
            double use=0;//该并联电路的总电阻
            ll rem=0;//该并联电路中最大的支路电阻
            int x=0;//当前结点位置
            for(ri i=0;i<to[rot].size();++i){
                //具体实现过程跟无向图转有向图过程差不多，由于前面已经转换过一遍，这个地方会好做很多
                ll sum=v[rot][i];
                x=to[rot][i];
                while(Cnt[x]==1){
                    sum+=v[x][0];
                    x=to[x][0];
                }
                ssum+=sum;
                use+=1.0/double(sum);
                rem=max(rem,sum);
            }
            va.push_back(1.0/use);
            rot=x;
            ans+=1.0/use;
            maxs.push_back(rem);
        }
        else{//如果是串连电路电阻直接累加就好了
            ans+=v[rot][0];
            rot=to[rot][0];
        }
    }
    printf("%.2lf\n",double(power)/ans);//输出最大电流
}
int main(){
    n=read(),m=read();
    for(ri i=1;i<=m;++i){
        int x=read(),y=read();
        char kind=getchar();
        int val=read();
        if(kind=='R'){
            g[x].push_back(y),g[y].push_back(x),++cnt[x],++cnt[y];
            vv[x].push_back(val),vv[y].push_back(val);
        }
        else{
            be=y,ed=x,power=val;
        }
    }
    dfs1(be);
    get_ans(be);
    double anss=double(power)/ans;//最小电流，初始为跟最大电流一样
    for(ri i=0;i<bp.size();++i){//在所有的并联电路中找到一个最小电流
        anss=min(anss,(va[i]/ans)*double(power)/maxs[i]);
    }
    printf("%.2lf",anss);
    return 0;
}

其实还有个地方可以优化一下,把公式优化一下可以得到
$I_{min}=\frac {{R_\texttt{总}}*U}{\frac {R}{R_\texttt{并}}}$ ，等式上方是一个定值
所以只要得到最大的$\frac {R}{R_\texttt{并}}$就可以了，这一步可以在算总电阻的时候一并计算
懒得改了