最近在刷巨巨们放出来的专题，然后没做几题就卡住了，果然还是太弱了T U T... 这次做到了一题01分数规划求解的生成树问题。 题目大意是这样的：给你一个无向完全图，每条边ｉ都有两个权值，长度a[ i ]，花费b[ i ]，需要选出其中的一些边构造一颗生成树，生成树需要满足条件：∑ b [ i ] / ∑ a [ i ]最小。 这样我还是先来介绍一下01分数规划吧~ 给定一个上述的问

一开始读题意可能有点难懂。 题意： 给你n个村庄的坐标点，它们都有一个海拔高度（你可以想象为三维空间）。现在让你给村庄通水，水道只能水平得建，即平行于地面。 每个水道的长度为村庄的水平距离（无视海拔高度），费用为两个村庄的海拔高度的差值。 现在只要修n-1条水道，让你求出  总费用/总长度  的最小比率。 思路： 分数规划 假设answer为最小的比率，answer <= su

题意：沙漠里的王国需要修建水渠，连接国都与村庄····。说白了求一棵树，每个点有三个坐标（x,y,z)。边的benifit为两点之间的距离，cost为两点的高度差。现在要求一棵树使得 cost / benift 最小。 题解：很显然任意两点之间都有边，所以是一个很稠密的图。用Prime。二分的话2800ms+, 迭代300ms+。 #include <cmath>#include <iost

题目： David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which a

首先解决这类问题一般有2种方法，，一是迭代法其次就是二分法，这里用到的主要是逼近的思想，，， 这是题目的要求是一颗生成树，但不是要求边权之和最大，所以不能直接用最小生成树来求，但我们可以把其转发为一个熟悉的问题。 设x1，x2，，，，，xm在集合{0,1}中取值，当且仅当xi=1时表示边i在生成树中出现，我们希望的是r =   ∑(cost[i] * x[i])/∑(benifit[i] *

POJ 2728 Desert King 题意：给出 n 个点的坐标和它的高度，求一颗生成树使得树上所连边的两点高度差之和除以距离之和最小。 思路：同样构造f(l)方程， 令∑hight / ∑dis = l，那么∑hight = l*∑dis, 令f(l) = ∑(hight - l*dis) ,题目所求是最小值 那么∑hight / ∑dis ≤ l 说明存在更优解，即f(l)

01分数规划的题目； 由于是完全图，所以求最小生成树的时候要使用prime算法。 否则的话很容易就超时了。 #include <iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>#include<stack>#include<math