来自FallDream的博客，未经允许，请勿转载，谢谢。
学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。有n个男生和n个女生参加舞会,一个男生和一个女生一起跳舞，互为舞伴。Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出 a[i][j] ，表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。Cathy还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 b[i][j]，表示第i个男生和第j个女生一起跳舞时的不协调程度。当然，还需要考虑很多其他问题。Cathy想先用一个程序通过a[i][j]和b[i][j]求出一种方案，再手动对方案进行微调。Cathy找到你，希望你帮她写那个程序。一个方案中有n对舞伴，假设没对舞伴的喜悦程度分别是a'1,a'2,...,a'n，假设每对舞伴的不协调程度分别是b'1,b'2,...,b'n。令C=(a'1+a'2+...+a'n)/(b'1+b'2+...+b'n),Cathy希望C值最大。
n,m<=100
这道题貌似挺好想的...考虑二分答案，然后假设我要check一个答案res是否合法，也就是check一下是否有方案满足$frac{sum a}{sum b}=res$。
很容易想到费用流，那么如果把b都变成b*res，把边的费用修改为res*b[i][j]-a[i][j],就转换为了最小费用最大流是否小等于0，就解决啦。
然而.....写的原始对偶跑的好慢 跑不过spfa....
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define eps 1e-9 #define S 0 #define T 201 #define INF 2000000000 using namespace std; int X;char ch; inline int read() { X = 0 , ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9'){X = X * 10 + ch - '0';ch = getchar();} return X; } int n,head[T+5],cnt=1; double a[105][105],b[105][105],ans,pi,d[T+5]; bool mark[T+5]; struct edge{int to,next,w;double c;}e[T*T*3]; deque<int> q; inline void ins(int f,int t,int w,double c) { e[++cnt]=(edge){t,head[f],w,c}; head[f]=cnt; e[++cnt]=(edge){f,head[t],0,-c};head[t]=cnt; } bool modlabel() { q.push_back(T); for(int i=S;i<T;i++)d[i]=INF;d[T]=0; while(!q.empty()) { int x=q.front();q.pop_front(); for(int i=head[x];i;i=e[i].next) if(e[i^1].w>eps&&d[x]+e[i^1].c<d[e[i].to]) { d[e[i].to]=d[x]+e[i^1].c; if(d[e[i].to]<=d[q.size()?q.front():0]) q.push_front(e[i].to); else q.push_back(e[i].to); } } for(int i=S;i<=T;i++) for(int j=head[i];j;j=e[j].next) e[j].c+=d[e[j].to]-d[i]; return pi+=d[S],d[S]<INF; } void build(double x) { cnt=1;memset(head,0,sizeof(head)); for(int i=1;i<=n;i++) { ins(S,i,1,0);ins(i+n,T,1,0); for(int j=1;j<=n;j++) ins(i,j+n,1,x*b[i][j]-a[i][j]); } } int dfs(int x,int f) { if(x==T)return ans+=pi*f,f; mark[x]=1;int used=0; for(int i=head[x];i;i=e[i].next) if(!mark[e[i].to]&&e[i].c<eps&&e[i].w>eps) { int w=dfs(e[i].to,min(f-used,e[i].w)); used+=w;e[i].w-=w;e[i^1].w+=w; if(used==f)return used; } return used; } int main() { n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) b[i][j]=read(); double l=0,r=10000,mid; while(r-l>1e-7) { mid=(l+r)/2.0; build(mid);ans=pi=0; while(modlabel()) do memset(mark,0,sizeof(mark)); while(dfs(S,INF)); if(ans<eps)l=mid; else r=mid; } printf("%0.6lf",(l+r)/2); return 0; }