MZOJ #82 总统竞选

分析

Part 1 模板题

最优比率生成树，01规划的模板题

但是！

他卡常

所以，孩子们还是乖乖写Dinkelbach吧

Part 2 01分数规划

欢迎造访我的blog：01分数规划

Part 3 最小值

我们需要求的是

中R的最小值，（x[i][j]代表这条边是否选）

稍微移项变换一下，就变成了：

可以看出，当R 减小的时候，左边的式子的值会增大。

若对于某一个确定的R值，左边的值是可以小于0的，

也就说明存在一个更小的R值能使左边的式子更加接近于0

这样，我们可以增大R 的值再次验证，直到找到最小的R值为止

当然可以二分解决，验证的时候，以cost[i][j]-R*dis[i][j]为权值求最小生成树

由于是一个完全图，n²的prim显然更优秀，用邻接矩阵存也方便

一切都很好

但是！

恭喜你，TLE快乐

这时，我们就需要更优秀的Dinkelbach算法

简单说来就是直接跳横截距

举个栗子（要糖炒的）

假如我们对于一个R值，找到了一个最小生成树的方案使得生成树上的所有边的权值cost[i][j]-R*dis[i][j]的和小于0

我们下一步就直接跳到令这颗生成树的所有权值和等于0的R上

理论上会快一点

不过这种算法与二分各有千秋，各有擅长的部分，根据题意选择正确适合的就好

看核心代码：

Prim

主程序

代码

  1 /********************
  2 User：Mandy
  3 Language:c++
  4 Problem:
  5 ********************/
  6 #include<bits/stdc++.h>
  7 
  8 using namespace std;
  9 
 10 typedef long long ll;
 11 typedef double dou;
 12 
 13 const int maxn = 1005;
 14 const dou esp = 1e-8;
 15 
 16 int t,n,size;
 17 double d[maxn];
 18 int from[maxn];
 19 double dis[maxn][maxn],cost[maxn][maxn];
 20 
 21 struct Node{
 22     int x,y,z;
 23 }node[maxn];
 24 
 25 
 26 template<class T>inline void read(T &x){
 27     x = 0;bool flag = 0;char ch = getchar();
 28     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
 29     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
 30     if(flag) x = -x;
 31 }
 32 
 33 template<class T>void putch(const T x){
 34     if(x > 9) putch(x / 10);
 35     putchar(x % 10 | 48);
 36 }
 37 
 38 template<class T>void put(const T x){
 39     if(x < 0) putchar('-'),putch(-x);
 40     else putch(x);
 41 }
 42 
 43 void file(){
 44     freopen("build3.in","r",stdin);
 45     freopen("build.out","w",stdout);
 46 }
 47 
 48 void readdata(){
 49     for(int i = 1;i <= n; ++ i){
 50         read(node[i].x);
 51         read(node[i].y);
 52         read(node[i].z);
 53     } 
 54 }
 55 
 56 double dist(int i,int j){
 57     return sqrt(((dou)node[i].x - node[j].x) * 
 58                 ((dou)node[i].x - node[j].x) + 
 59                 ((dou)node[i].y - node[j].y) * 
 60                 ((dou)node[i].y - node[j].y));
 61 }
 62 
 63 void init(){
 64     for(int i = 1;i <= n; ++ i){
 65         for(int j = i;j <= n; ++ j){
 66             dis[i][j] = dist(i,j);
 67             dis[j][i] = dis[i][j];
 68             cost[i][j] = abs((double)node[i].z - node[j].z);
 69             cost[j][i] = cost[i][j];
 70         }
 71     }
 72 }
 73 
 74 double Prim(double r){
 75     int cnt = 1;t = 0;double c = 0,D = 0;
 76     for(int i = 1;i <= n;++i) 
 77         d[i] = cost[1][i]-r*dis[1][i],from[i] = 1;
 78     d[1] = -2e9;
 79     for(int j = 1;j <= n; ++ j){
 80         double cur = 2e9;int id = 0;
 81         for(int i = 1;i <= n; ++ i){
 82             if(d[i]!=-2e9 && d[i] < cur){
 83                 cur = d[i];    id = i;
 84             }
 85         }
 86         t += cur;cnt++;d[id] = -2e9;
 87         c += cost[from[id]][id];
 88         D += dis[from[id]][id];
 89         if(cnt == n) break;
 90         for(int i = 1;i <= n; ++ i) {
 91             if(d[i] > cost[id][i]-r*dis[id][i]){
 92                 d[i] = cost[id][i]-r*dis[id][i];
 93                 from[i] = id;
 94             }
 95         }
 96     }
 97     if(t < esp) return c/D;
 98     else return -2e9;
 99 }
100 
101 void work(){
102     double ans = (double)7;
103     while(1){
104         double R = Prim(ans);
105         if(R == -2e9||fabs(ans - R) <= esp) break;//fabs!!
106         //直接判断是否相等就好，r不会等于-2e9 
107         ans = R;
108     }
109     printf("%.3lf
",ans);
110 }
111 
112 int main(){
113 //    file();
114     while(~scanf("%d",&n)){
115         if(!n) break;
116         size = 0;
117         readdata();
118         init();
119         work();
120     }
121     return 0;
122 }

View Code

最后偷偷放个题解