给定一张 n ( 100 ) ∗ 2 n(100)*2 n(100)∗2个点的二分图，第 i i i个左侧点与第 j j j个右侧点之间有两个属性： a i j , b i j a_{ij},b_{ij} aij,bij.
选择一种n条边的匹配方案，使得 Σ a / Σ b \Sigma a/\Sigma b Σa/Σb最大
套一层01分规的壳，二分查找 F ( x ) = m a x d { a i j − x b i j } F(x)=max_d\{a_{ij}-xb_{ij}\} F(x)=maxd{aij−xbij}这个减函数的零点。
需要找到 c i j = a i j − x b i j c_{ij}=a_{ij}-xb_{ij} cij=aij−xbij最大的二分图最大匹配。
考虑费用流：
源点-左侧点，容1费0；右侧点-汇点，容1费0左侧点-右测点，容1费 c i c_i ci求最大费用最大流需要把费用改成double，注意求最大费用时所有费用要变成相反数。
/* LittleFall : Hello! */ #include <bits/stdc++.h> using namespace std; using ll = long long; inline int read(); const int M = 256, MOD = 1000000007; const double INF = 1e16; inline int dcmp(double a, double b) { if(fabs(a-b)<1e-8) return 0; return a>b ? 1 : -1; } //MCMF.cpp 最小费用最大流. struct MinCostMaxFlow { struct Edge{int from, to, cap, flow;double cost;}; vector<Edge>edges; //边表,edges[i]和edges[i^1]互为反向弧 vector<int>G[M]; //邻接表,G[i][j]表示节点i的第j条边在e中的序号 void addEdge(int from, int to, int cap, double cost) { edges.push_back({from, to, cap, 0, cost}); edges.push_back({to, from, 0, 0, -cost}); G[from].push_back(edges.size() - 2); G[to].push_back(edges.size() - 1); } // 当前节点：是否在队列中，上一条弧编号, 可改进量, 最短距离（费用） int inq[M], lst[M], add[M]; double dis[M]; bool spfa(int s, int t, int &flow, double &cost) { for(int i=0; i<M; ++i) dis[i] = INF; memset(inq, 0, sizeof(inq)); queue<int> q; //查找增广路 dis[s] = lst[s] = 0; add[s] = MOD; q.push(s); inq[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for(int eid : G[u]) { Edge &e = edges[eid]; if(e.cap > e.flow && dis[e.to] > dis[u] + e.cost) { dis[e.to] = dis[u] + e.cost; lst[e.to] = eid; add[e.to] = min(add[u], e.cap - e.flow); if(!inq[e.to]) { q.push(e.to); inq[e.to] = 1; } } } } //printf("cost=%.3f\n",cost ); if(dcmp(dis[t], INF)>=0) return false; // 增广 flow += add[t]; cost += dis[t] * add[t]; for(int u = t; u != s; u = edges[lst[u]].from) { edges[lst[u]].flow += add[t]; edges[lst[u] ^ 1].flow -= add[t]; } return true; } pair<int,double> solve(int s, int t) { int flow = 0; double cost = 0; while(spfa(s, t, flow, cost)); return {flow, cost}; } }; int A[M][M], B[M][M]; int main(void) { #ifdef _LITTLEFALL_ freopen("in.txt","r",stdin); #endif int 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 = 1e6+1; while(dcmp(l,r)<0) { double m = (l+r)/2; int src = 0, dst = 201; MinCostMaxFlow mcmf; for(int i=1; i<=n; ++i) { mcmf.addEdge(src, i, 1, 0); mcmf.addEdge(i+100, dst, 1, 0); for(int j=1; j<=n; ++j) mcmf.addEdge(i, j+100, 1, -(A[i][j]-m*B[i][j])); } double F = -mcmf.solve(src, dst).second; if(dcmp(F,0)>=0) l = m; else r = m; } printf("%.6f\n",l ); return 0; } inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }