P4951 题解
Peter0701
2019-02-12 15:09:59
### **二分答案好题！**
这题虽然年代久远（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 $ 小于该值则答案过小，反之答案过大。
至此，本题结束！其余细节见下方代码。有疑问和指正评论区见，谢谢观看！
扩展阅读：[最优比率生成树](https://www.jianshu.com/p/d40a740a527e)
本题代码：
```cpp
#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;
}
```