题目求一种方案, 使得图全连通并且所有边费用与距离之商最小
\(\sum_{i∈e}cost_i\) 除以 \(\sum_{i∈e}dis_i\) 最小
可以考虑二分求解
可以假设这个值小于等于 L 时存在一个解, 然后检查是否存在这个解, 如果不存在说明 L 取小了
问题是为什么要假设 "存在", 事实上如果假设 "任意", 那么就要检查每种可能都要小于, 就很麻烦, 所以把求任意改为求存在是最好的
但是这个解很难找... 又不能一个个检验, 但是除了 L 以外的数都是输入数据.
对式子进行变形, 得:
\[L*\sum_{i∈e}dis_i-\sum_{i∈e}cost_i>= 0\]
\[\sum_{i∈e}dis_i*L-\sum_{i∈e}cost_i>= 0\]
分数规划要通过列式子来找到某个关系, 最后把存在这个解这个求解问题转化为判定正负问题
对式子要灵活变换 把问题转化为求存在问题
比如说把某些问题转化为 求负环, 若求得负环, 则此答案可行, 这样一举解决了判断是否存在解的问题 形式上就是乘个负号, 把式子变为小于等于 0
另外说下 EPS 的作用, 因为二分的是实数, 而因为精度问题 l 和 r 永远不会重合, 这时就需要设 EPS, 当 l 和 r 的差小于 EPS 时认为他们相同, 而判断正负的时候不需要, 因为这时说明 L 确实取小了
相应的还有愤怒的小鸟那题, 求出的抛物线因为精度打不到目标, 但按理来说是该打到的
注意二分的时候实数二分或许用位运算来代替 (l+r)/2 不太好... 毕竟不是整数型
哎, L 的上界难以估计, 大了就会 T, 我取到 1000 卡了过去...
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- #define debug(x) cerr <<#x << "=" << x << endl;
- const int MAXN = 1000 + 10;
- const double EPS = 1e-6;
- const int INF = (1<<30) / 3;
- typedef long long ll;
- int n,last[MAXN],tot,fa[MAXN],vis[MAXN];
- double ans, esum, l,ttem[MAXN][MAXN],ddis[MAXN][MAXN],d[MAXN],gra[MAXN][MAXN];
- struct viii{
- int x,y,z;
- }vil[MAXN];
- int abab(int x) {
- if(x < 0) return -x;
- return x;
- }
- void prim() {
- for(int i=1; i<=n; i++) {
- d[i] = -INF;
- }
- memset(vis, 0, sizeof(vis));
- for(int i=1; i<=n; i++) {
- int x = 0;
- for(int j=1; j<=n; j++) {
- if(!vis[j] && (x == 0 || d[j]> d[x])) x = j;
- }
- vis[x] = 1;
- for(int j=1; j<=n; j++) {
- if(!vis[j]) d[j] = max(d[j], gra[x][j]);
- }
- }
- }
- int main() {
- while(1) {
- esum = 0.0;
- cin>> n;
- if(n == 0) break;
- for(int i=1; i<=n; i++) {
- cin>> vil[i].x>> vil[i].y>> vil[i].z;
- }
- for(int i=1; i<=n; i++) {
- for(int j=1; j<=n; j++) {
- double temp = 0;
- int sum = 0;
- int x1 = vil[i].x, y1 = vil[i].y, x2 = vil[j].x, y2 = vil[j].y;
- sum = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
- temp = (double)sum;
- temp = sqrt(temp);
- int dist = abab(vil[i].z - vil[j].z);
- ttem[i][j] = ttem[j][i] = dist;
- ddis[i][j] = ddis[j][i] = temp;
- esum += temp;
- }
- }
- //double l = 0, r = esum;
- double l = 0, r = 1000;
- while(r-l>= EPS) {
- double mid = (l+r)/2;
- tot = 0;
- for(int i=1; i<=n; i++) {
- for(int j=1; j<=n; j++) {
- if(i != j)
- gra[i][j] = gra[j][i] = ddis[i][j] * mid - ttem[i][j];
- }
- }
- double mst = 0.0;
- prim();
- for(int i=2; i<=n; i++) {
- mst += d[i];
- }
- if(mst>= 0) {
- r = mid;
- ans = mid;
- } else {
- l = mid;
- }
- }
- printf("%.3lf\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2807356.html