网络战争
注:如果Latex挂掉了请告知我,或者用typora/vscode打开
求一个平均权值最小的割集。
考虑分数规划。存在一个平均值不大于$x$的割集等价于:
$$
\exists C,\dfrac{\sum_{e\in C}w(e)}{|C|}\le x
$$
$$ \Rightarrow \exists C,\sum_{e\in C}(w(e)-x)\le 0 $$
故 存在一个平均值不大于$x$的割集$\Leftrightarrow$将边权全部减少$x$后,最小割权值不超过0.二分答案+最大流 即可。
注意图中会出现负权边,没法直接最大流,但最小割中必然包含所有负权边,提前选上即可。
浮点数最大流真毒瘤啊
struct one{int u,v,w;}e2[MAXM];
int n,m,S,T;
bool check(double k)
{
cnt=1;
for(int i=1;i<=n;++i)last[i]=0;
double sum=0;
for(int i=1;i<=m;++i)
if(e2[i].w<=k)sum+=e2[i].w-k;
else adde(e2[i].u,e2[i].v,e2[i].w-k),adde(e2[i].v,e2[i].u,e2[i].w-k);
return Dinic(S,T,n)+sum<=0;
}
int main()
{
n=read(),m=read(),S=read(),T=read();
for(int i=1;i<=m;++i)e2[i].u=read(),e2[i].v=read(),e2[i].w=read();
double l=0,r=1e7;
while(r-l>2e-3)
{
double mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
printf("%.2lf",l);
return 0;
}
$\text{wh}$神!