转载

[转载] $Luogu$ $P4951$ 题解

阅读原文

二分答案好题!

这题虽然年代久远(2001),但是USACO出题者的智慧duliu确实让我们惊叹。

题意是说给出一张无向图,每条边有一个时间 $ t $ 和一个花费 $ c $ ,另给出酬劳 $ f $ ,求平均时间的利润。

不妨设平均时间的利润为 $ ans $ ,则 $ ans = \frac{ f - \sum{ c_i } }{ \sum{ t_i } }$ 。对式子进行变换易得 $ f - \sum{ c_i } - ans * \sum{ t_i } = 0 $ 。

令函数 $ f ( ans ) = f - \sum{ c_i } - ans * \sum{ t_i } $ ,显然 $ f ( ans ) $ 是具有单调性的,在本题范围内单调递减。

因此,我们可以采用二分答案的做法来解决这道题目,对 $ ans $ 进行二分。

当然,二分答案的精髓永远是 $ check $ 函数。本题中为了检验答案的合法性,由前面的式子不妨将每条边的权值设定为 $ c_i + ans * t_i $ ,通过跑一遍 $ Kruskal $ 很容易算出$ \sum{ c_i } + ans * \sum{ t_i } $ ,若 $ f $ 小于该值则答案过小,反之答案过大。

至此,本题结束!其余细节见下方代码。有疑问和指正评论区见,谢谢观看!

扩展阅读:最优比率生成树

本题代码:

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,m,f,fa[405]; long long mid,l,r=2e15; struct Edge { int x; int y; int c; int t; double w; }edge[10005]; inline bool cmp(Edge a,Edge b) { return a.w<b.w; } inline int find(int x) { if(fa[x]==x) return x; return fa[x]=find(fa[x]); } inline bool check(long long mid) { for(register int i=1;i<=m;i++) edge[i].w=mid/(3e6+0.0)*edge[i].t+edge[i].c; int tmp=1; sort(edge+1,edge+m+1,cmp); for(register int i=1;i<=n;i++) fa[i]=i; double k=f+1e-12; for(register int i=2;i<=n;i++) { while(tmp<=m&&find(edge[tmp].x)==find(edge[tmp].y)) tmp++; fa[find(edge[tmp].x)]=find(edge[tmp].y),k-=edge[tmp].w; if(k<0) return false; } return true; } int main() { n=read(); m=read(); f=read(); for(register int i=1;i<=m;i++) { edge[i].x=read(); edge[i].y=read(); edge[i].c=read(); edge[i].t=read(); } if(!check(0)) { printf("0.0000\n"); return 0; } while(l<r) { mid=(l+r)>>1; if(check(mid+1)) l=mid+1; else r=mid; } printf("%0.4lf\n",l/(3e6+0.0)); return 0; }

转载于:https://www.cnblogs.com/Peter0701/p/11298181.html

正文到此结束
本文目录