【poj2976】$Dropping\ tests$——初步接触分数规划
题目大意
给出两个有$n$个元素的序列$A,B$
分别选择$n-k$个元素，询问$\frac{\sum a_i}{\sum b_i}$的最大值
数据范围
$1\leqslant n\leqslant 1000,0\leqslant k< n$
题解——二分
入门题是一道裸题，就不会把人吓跑啦 
设，$x=\frac{\sum a_i}{\sum b_i}\ \rightarrow\ \sum a_i-x\times \sum b_i=0$
令，$f(x)=max(\sum a_i-x\times \sum b_i)$，可以得到$f(x)$是一个单调递减的函数
新函数是非分式的规划，有以下性质设，原规划最优解为$x^{\prime}$
$f(x)> 0\ \leftrightarrow\ x< x^{\prime}$
$f(x)= 0\ \leftrightarrow\ x= x^{\prime}$
$f(x)< 0\ \leftrightarrow\ x> x^{\prime}$
然后给出简略的证明 
$f(x)>0$，也就意味着存在$\sum a_i-x\times \sum b_i>0\ \rightarrow\ \frac{\sum a_i}{\sum b_i}>x$，则肯定有更优解，即$x< x^{\prime}$
另外两个，也是类似的证法，这里不详细给出
然后怎么来做这道题呢?$f(x)$是单调递减的函数，因此可以每次二分$x$
然后处理得到$a_i-x\times b_i$，再排序得到最大的$n-k$个值，求和就是$f(x)$
最后利用性质判断，继续二分即可
程序——二分
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define maxn 1050
#define esp 1e-5
using namespace std;
int n,k;
double a[maxn],b[maxn],f[maxn];
double check(double x){
double sum=0;
For(i,1,n) f[i]=a[i]-x*b[i];
sort(f+1,f+n+1);
For(i,k+1,n) sum+=f[i];
return sum;
}
int main(){
while (scanf("%d%d",&n,&k),n|k){
For(i,1,n) scanf("%lf",&a[i]);
For(i,1,n) scanf("%lf",&b[i]);
double l=(double)0,r=(double)1;
while (r-l>esp){
double mid=(double)(l+r)/2;
if (check(mid)>0) l=mid;
else r=mid;
}
printf("%.0lf\n",(double)l*100);
}
return 0;
}题解——$Dinkelbach$
分数规划问题，实际上有两种解法
我们知道，当$f(x)> 0\ $时，可以得到一个比$x$更优的解，因此缩短一半的范围继续二分，这是一种思路
可是为什么不直接把$x$调整为那个更优的解呢?
那么就出现了第二种思路，每次把$x$调整为得到的更优解，直到满足精度要求
程序——$Dinkelbach$
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define maxn 1050
#define esp 1e-5
using namespace std;
int n,k;
struct data{double a,b,f;}q[maxn];
inline int cmp(data x,data y){return x.f<y.f;}
int main(){
while (scanf("%d%d",&n,&k),n|k){
For(i,1,n) scanf("%lf",&q[i].a);
For(i,1,n) scanf("%lf",&q[i].b);
double l,ans=0;
do{
l=ans;
For(i,1,n) q[i].f=q[i].a-l*q[i].b;
sort(q+1,q+n+1,cmp);
double x=0,y=0;
For(i,k+1,n) {x+=q[i].a;y+=q[i].b;}
ans=x/y;
}while (fabs(l-ans)>esp);
if (ans>1) ans=1;
printf("%.0lf\n",(double)ans*100);
}
return 0;
}【poj2728】$Desert\ King$——最优比率生成树
题目大意
给出一个$n$个点的完全图，每条边有两个权值$cost_i,len_i$
询问一个生成树$T$，其中$\frac{\sum cost_i}{\sum len_i}(i\in T)$的最小值
数据范围
$2\leqslant n\leqslant 1000$
题解
从一个序列延伸到一个图，这又怎么办呢
核心不变，还是不断更新答案求出$f(x)$，然后逼近更优解，但是怎么求出$f(x)$呢？
如果当前更新答案为$x$，建新图，每条边边权为$(cost_i-x\times len_i)$
由于题目求的是最小值，因此$f(x)=\min(\sum cost_i-x\times \sum len_i)(i\in T)$
所以跑一遍新图的最小生成树就可以得到$f(x)$
值得注意的是，在完全图上最好用$prim$来跑最小生成树
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define maxn 1050
#define esp 1e-5
#define inf 0x7ffffff
using namespace std;
int n,vis[maxn],p[maxn];
double a,b,c,ans,mx,mn;
double x[maxn],y[maxn],h[maxn];
double len[maxn][maxn],cost[maxn][maxn];
double v[maxn][maxn],dis[maxn];
inline double sqr(double x){return x*x;}
inline void prim(double x){
a=b=c=0;
For(i,1,n) For(j,1,n)
v[i][j]=cost[i][j]-x*len[i][j];
For(i,1,n) dis[i]=inf,vis[i]=0;
dis[1]=p[1]=0;
int num=0,h=1;
while(1){
vis[h]=1;
a+=cost[p[h]][h];
b+=len[p[h]][h];
c+=dis[h];
if (++num>=n) break;
For(i,1,n)
if (!vis[i]&&dis[i]>v[h][i])
dis[i]=v[h][i],p[i]=h;
mn=(double)inf;
For(i,1,n)
if (!vis[i]&&dis[i]<mn){
mn=dis[i];
h=i;
}
}
}
int main(){
while (scanf("%d",&n),n){
For(i,1,n) scanf("%lf%lf%lf",&x[i],&y[i],&h[i]);
mx=(double)-inf;
For(i,1,n) For(j,1,n){
len[i][j]=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
cost[i][j]=fabs(h[i]-h[j]);
mx=max(mx,cost[i][j]);
}
ans=(double)mx*n;
do{
prim(ans);
ans=a/b;
}while (fabs(c)>esp);
printf("%.3lf\n",ans);
}
return 0;
}【poj3621】$Sightseeing\ Cows$——最优比率环
题目大意
给出一个有$L$个点$P$条边的有向图，每个点上有点权$F_i$，每条边上有边权$T_i$
询问在任意一个点为起点的回路$C$，其中$\frac{\sum F_i}{\sum T_i}(i\in C)$的最大值
数据范围
$2\leqslant L\leqslant 1000,2\leqslant P\leqslant 5000$
$1\leqslant F_i,T_i\leqslant 1000$
题解
在一个环上，点和边个数相等，证明过程略$\cdots$
所以对于一个环，可以把点和边放在一起处理
也就是说，如果当前更新答案为$x$，建新图，边($A\rightarrow B$)的边权为($x\times T_{A\rightarrow B}-F_B$)
为了得到$f(x)=\max(x\times \sum T_i-\sum F_B)(i\in C)$，就要去判断新图中是否存在正环
明显存在正环的时候有$f(x)>0$，同理$\cdots$，所以二分答案就好啦
补充一下，资瓷一下判断图中是否存在正环，简单跑一遍$dfs$即可，强行$spfa$的速度非常慢
程序
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define esp 1e-5
#define maxn 1050
#define maxm 5050
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,et,flag;
struct edge{int to,next,t;}e[maxm];
int last[maxn],f[maxn],vis[maxn];
double dis[maxn];
inline void addedge(int u,int v,int t){
e[++et].to=v,e[et].next=last[u],e[et].t=t;
last[u]=et;
}
void dfs(int h,double x){
vis[h]=1;
goedge(i,h)
if (dis[e[i].to]<dis[h]+(double)f[e[i].to]-(double)x*e[i].t){
if (vis[e[i].to]){
flag=1;
return;
}
dis[e[i].to]=dis[h]+(double)f[e[i].to]-(double)x*e[i].t;
dfs(e[i].to,x);
if (flag) return;
}
vis[h]=0;
}
inline int check(double x){
For(i,1,n) vis[i]=dis[i]=0;
flag=0;
For(i,1,n){
dfs(i,x);
if (flag) return 1;
}
return 0;
}
int main(){
while (~scanf("%d%d",&n,&m)){
For(i,1,n) f[i]=read();
For(i,1,m){
int u=read(),v=read(),t=read();
addedge(u,v,t);
}
double l=0,r=1000;
while (r-l>esp){
double mid=(l+r)/2;
if (check(mid)) l=mid;
else r=mid;
}
printf("%.2lf\n",l);
}
return 0;
}
鄂公网安备 42010202000505 号