P4946 流量计算题解
前置芝士：
-
初中物理（大概初一初二水平？）
-
图论（会建图就行）
-
dfs
此处先以样例三为例
在读入数据之后很轻松就能建出一个这样的图，其中16是起点，1是终点
但是电流是带有方向的，而上面这个图由于是无向边，不能很好地模拟电流
于是考虑把上面的图转换成有向图
这样子就方便多了，只要遍历一遍图就可以求出总电阻了（电阻公式不用我多说了吧）
根据串连电路的性质，最大电流肯定就是总电压除以总电阻
而最小电流则肯定出现在某条并联电路的支路上面
这里以上图中15->11这一段电路为例，设这一段的电阻为
于是求其中任意一段的电流就是
剩下的就是代码实现了
#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;
}其实还有个地方可以优化一下,把公式优化一下可以得到