01分数规划 题目传送门
【POJ|POJ2728 Desert King】题目大意：有 nn 个点，两点之间都有道路，道路有两个权值： len=l e n = 两点之间距离， cost=c o s t = 两点高度之差。求使 ∑cost∑len∑ c o s t ∑ l e n 最小的生成树的该比值。
这题就是求最优比例生成树。二分比值 midm i d ，把每条边的权值改为 cost[i]?mid?len[i]c o s t [ i ] ? m i d ? l e n [ i ] ，跑最小生成树和0比较即可。
代码（用G++交）：
#include
#include
#include
#include
#define N 1005
#define eps 1e-8
#define sqr(x) ((x)*(x))
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
typedef double DB;
struct edge{DB d,c;
} ed[N][N];
int n,x[N],y[N],z[N];
bool f[N];
DB d[N];
inline bool pd(DB x){
memset(f,false,sizeof(f));
f[1]=true;
DB ret=0;
for (int i=1;
i<=n;
i++)
d[i]=ed[1][i].c-x*ed[1][i].d;
for (int i=1;
i<=n-1;
i++){
DB mn=1e50;
int now;
for (int j=1;
j<=n;
j++)
if (!f[j]&&d[j]eps)
if (pd(mid=(l+r)/2)) r=mid-1e-6;
else l=mid+1e-6;
printf("%.3f\n",l);
}
return 0;
} 推荐阅读
- POJ 1364 King 差分约束系统
- POJ 8496 特殊密码锁
- POJ|POJ 1364 King 差分约束系统 SPFA
- POJ|POJ 2241 The Tower of Babylon 笔记