首先分数规划是一类决策性问题
一般形式是：
\[
\lambda=\frac{f(x)}{g(x)}
\]
其中\(f(x)\)和\(g(x)\)都是连续的实值函数，然后要求\(\lambda\)的最大值或最小值
这类问题中，研究较多的是\(01\)分数规划，也就是求
\[
\lambda=\frac{\sum (f_i*x_i)}{\sum (g_i*x_i)}
\]
其中\(x_i \in \{0,1\}\)，其他条件和普通分数规划一样，求\(\lambda\)的最大或最小值
接下来我们讨论的是\(01\)分数规划
具体求解
求解\(01\)分数规划的问题很重要的一个思想就是二分
某种程度上可以理解为一种二分答案，只是判断的方式稍微有一点点不同
我们处理一下上面的\(\lambda\)的表达式：
\[
\begin{aligned}
\sum(f_i*x_i)&=\lambda \sum(g_i*x_i)\\
\end{aligned}
\]
移一下项变成：
\[
\sum(f_i*x_i)-\lambda\sum(g_i*x_i)=0
\]
这个就是我们需要的一个式子啦
具体什么意思呢？
以求解表达式的最大值为例，考虑二分最终的答案
我们将最终的答案记为\(ans\)，记当前二分到的\(mid\)为\(\lambda'\)，那么上面这个表达式应该满足：
1、\(ans<\lambda'\)时，\(max(\frac{\sum (f_i*x_i)}{\sum (g_i*x_i)})=ans<\lambda'\)，也就是\(max(\sum(f_i*x_i)-\lambda’\sum(g_i*x_i))<0\)
2、\(ans=\lambda'\)时，则上面这个表达式的值为\(0\)
3、\(ans>\lambda'\)时，则上面这个表达式的值\(>0\)
所以我们要做的就是在一个比较合理的时间内求出\(max(\sum(f_i*x_i)-\lambda’\sum(g_i*x_i))\)（或者\(min\)）就好啦
这样的题目往往会跟一些其他的算法结合起来，比如环啊生成树啊之类的
接下来放几道例题帮助理解
例题们
首先是两道相对来说基础一点的：
Portal -->bzoj4819新生舞会
看到答案的那个形式。。那就分数规划咯。。
我们现在相当于是要求：
\[
\frac{\sum\limits_{i=1}^{n} \sum\limits_{j=1}^n a_{i,j}*x_{i,j}}{\sum\limits_{i=1}^{n} \sum\limits_{j=1}^n b_{i,j}*x_{i,j}}
\]
这个东西的最大值
其中\(x_{i,j}\in \{0,1\}\)表示\(i\)和\(j\)是否是舞伴
那明显是一个\(01\)分数规划的形式，套用上面讲到的方法，现在问题转变成如何判断
\[
max(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^n a_{i,j}*x_{i,j}-\lambda'\sum\limits_{i=1}^{n} \sum\limits_{j=1}^n b_{i,j}*x_{i,j})
\]
与\(0\)的关系
这里我们可以考虑用费用流来求解，具体建图相对来说还是比较好想的：
男生看成\(1\)到\(n\)号，女生看成\(1+n\)到\(n+n\)号
1、源点\(S\)往\(1\)到\(n\)（男生）都连一条费用为\(0\)，流量为\(1\)的边
2、男生\(i\)（也就是\(i\)号点）往女生\(j\)（也就是\(j+n\)号点）连一条费用为\((a_{i,j}-\lambda' b_{i,j})\)，流量为\(1\)的边
3、\(1+n\)到\(n+n\)号（女生）往汇点\(T\)连一条费用为\(0\)，流量为\(1\)的边
然后大力跑最大费用最大流就好啦
代码大概长这个样子：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; const int N=110,inf=2147483647; const double eps=1e-8; struct xxx{ int x,y,nxt,r; double c; }a[N*N*10+10]; queue<int> q; int h[N*2],pre[N*2]; double cost[N*2]; bool vis[N*2]; int A[N][N],B[N][N]; int n,m,tot,S,T; void add(int x,int y,double c,int r); bool spfa(double &rec); void build(double mid); void solve(); int main(){ #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); #endif scanf("%d",&n); for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) scanf("%d",&A[i][j]); for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) scanf("%d",&B[i][j]); solve(); } void add(int x,int y,double c,int r){ //printf("%d %d %.6lf %d\n",x,y,c,r); a[++tot].y=y; a[tot].x=x; a[tot].nxt=h[x]; h[x]=tot; a[tot].r=r; a[tot].c=c; a[++tot].y=x; a[tot].x=y; a[tot].nxt=h[y]; h[y]=tot; a[tot].r=0; a[tot].c=-c; } bool spfa(double &rec){ while (!q.empty()) q.pop(); int v,u; q.push(S); cost[S]=0; pre[S]=-1; for (int i=S+1;i<=T;++i) cost[i]=-inf,vis[i]=false; vis[S]=true; while (!q.empty()){ v=q.front(); q.pop(); for (int i=h[v];i!=-1;i=a[i].nxt){ u=a[i].y; if (!a[i].r) continue; if (cost[u]<cost[v]+a[i].c){ cost[u]=cost[v]+a[i].c; pre[u]=i; if (!vis[u]) vis[u]=true,q.push(u); } } vis[v]=false; } if (cost[T]==-inf) return false; int flow=inf; u=T; while (pre[u]!=-1) flow=min(flow,a[pre[u]].r),u=a[pre[u]].x; rec+=1.0*flow*cost[T]; u=T; while (pre[u]!=-1) a[pre[u]].r-=flow,a[pre[u]^1].r+=flow,u=a[pre[u]].x; return true; } void build(double mid){ tot=-1; S=0; T=2*n+1; for (int i=S;i<=T;++i) h[i]=-1; for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) add(i,j+n,1.0*A[i][j]-mid*B[i][j],1); for (int i=1;i<=n;++i) add(S,i,0,1),add(i+n,T,0,1); } bool check(double mid){ double rec=0; build(mid); while (spfa(rec)); return rec>0; } void solve(){ double l=0,r=10000,mid,ans; while (r-l>eps){ mid=(l+r)*0.5; if (check(mid)) ans=mid,l=mid; else r=mid; } printf("%.6lf\n",ans); }