almost 4 years ago

因为卡kruskal所以tle了==+懒得改成prim
最优比例生成树:
一、对于比例最大:大神的说明:http://www.cnblogs.com/lotus3x/archive/2009/03/21/1418480.html
解法之一 0-1分数规划
设x[i]等于1或0, 表示边e[i]是否属于生成树.
则我们所求的比率 r = ∑(benifit[i] * x[i]) / ∑(cost[i] * x[i]), 0≤i 为了使 r 最大, 设计一个子问题---> 让 z = ∑(benifit[i] * x[i]) - l * ∑(cost[i] * x[i]) = ∑(d[i] * x[i]) 最大 (d[i] = benifit[i] - l * cost[i]) , 并记为z(l). 我们可以兴高采烈地把z(l)看做以d为边权的最大生成树的总权值.
然后明确两个性质:
 1. z单调递减
  证明: 因为cost为正数, 所以z随l的减小而增大.
 2. z( max(r) ) = 0
  证明: 若z( max(r) ) < 0, ∑(benifit[i] * x[i]) - max(r) * ∑(cost[i] * x[i]) < 0, 可化为 max(r) < max(r). 矛盾;
   若z( max(r) ) >= 0, 根据性质1, 当z = 0 时r最大.
到了这个地步, 七窍全已打通, 喜欢二分的上二分, 喜欢Dinkelbach的就Dinkelbach.
复杂度
时间 O( O(MST) * log max(r) )
空间 O( O(MST) )
二、若要求比例最小:可列出方程(benifit[1]+...benifit[n])/(cost[1]+...cost[n])<=k
在方程满足的情况下,二分不断缩小k的值即可
为了判定方程满足,将其化为:sum(benifit[i]-k*cost[i])<=0即sum(k*cost[i]-benifit[i])>=0
设z(i)= k*cost[i]-benifit[i];
此时只要求出一个生成树满足方程即可,所以求最大生成树,其值>=0即为满足
MARK:对于z的两条性质还要理解一下……
*/
``` c++

include

include

include

include

include

define maxn 1001

define maxm 1000001

using namespace std;
struct wide
{
int x,y,bs;double w,bx;
} a[maxm];
struct node
{
int x,y,h;
} b[maxn]={0};
long long ls[maxm]={0};
int n,m,lsn=0,widen=0;double temp;
int fa[maxn];
int find(int x)
{
if (fa[x]==x) return x;return fa[x]=find(fa[x]);
}
int readln()
{
char c=getchar();int bj=1,result=0;
while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
if (c=='-') bj=-1,c=getchar();
while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
return result*bj;
}
bool cmp(const wide a,const wide b)
{
return a.w }
int main()
{
int left,right,mid,i,j,k,xx,yy,tot;
double temp,result;
while (true)
{
n=readln();
widen=0;lsn=0;
if (n==0) return 0;
for (i=1;i for (i=1;i for (j=i+1;j {
a[++widen].x=i;a[widen].y=j;a[widen].bs=abs(b[i].h-b[j].h);
a[widen].bx=sqrt((b[i].x-b[j].x)*(b[i].x-b[j].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y));
ls[++lsn]=(long long)((a[widen].bs/a[widen].bx+0.0005)*1000);
}
sort(ls+1,ls+lsn+1);
lsn=unique(ls+1,ls+lsn+1)-ls-1;
right=lsn;left=1;
while (left {
mid=(left+right)>>1;
temp=ls[mid]/1000.0;
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=widen;i++) a[i].w=a[i].bx*temp-a[i].bs;
sort(a+1,a+widen+1,cmp);
result=0.0;tot=0;
for (i=widen;i>=1;i--)
{
xx=find(a[i].x);yy=find(a[i].y);
if (xx!=yy) {fa[xx]=yy;result+=a[i].w;
tot++;if (tot==n-1) break;}
}
if (result>=0) right=mid;
else left=mid+1;
}
temp=ls[left]/1000.0;
printf("%.3lf\n",temp);
}
}
```

← 【poj1639】【度限制最小生成树】Picnic Planning little of 斜率优化 →
 
comments powered by Disqus