现在怎么做的题都这么水了。。
题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=4819
(luogu) https://www.luogu.org/problemnew/show/P3705
题解: 常规分数规划套路，二分答案(mid)之后边权改变为(a_{i,j}-mid imes b_{i,j})求最大费用最大流即可。（我求成最小费用了，真厉害）
从网上学到一种神奇做法: 迭代
每次按照上次的答案(mid)来计算，顺便求出方案，据此求出这次的答案，若两次答案差大于一阈值则继续迭代
至于为什么是对的。。。只能说感性理解吧（大雾）
这样的话次数会小很多！但是这种网络流题求方案比较容易，如果是一些求答案很简单但是求方案很麻烦的问题，迭代就不适用了。
代码
迭代
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<algorithm>
#include<cmath>
using namespace std;
const double INF = 1e9;
const double EPS = 1e-8;
namespace MaxFlowMinCost
{
const int N = 202;
const int M = 10200;
struct Edge
{
int u,v,w,nxt,rev; double c;
} e[(M<<1)+3];
int fe[N+3];
int que[N+3];
bool inq[N+3];
double dis[N+3];
int lst[N+3];
int n,en,s,t,mf; double mc;
void clear()
{
for(int i=1; i<=n; i++) fe[i] = que[i] = lst[i] = 0;
for(int i=1; i<=en; i++) e[i].u = e[i].v = e[i].w = e[i].nxt = e[i].rev = 0,e[i].c = 0.0;
n = en = s = t = mf = 0; mc = 0.0;
}
void addedge(int u,int v,int w,double c)
{
// printf("addedge %d %d %d %lf
",u,v,w,c);
en++; e[en].u = u; e[en].v = v; e[en].w = w; e[en].c = c;
e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;
en++; e[en].u = v; e[en].v = u; e[en].w = 0; e[en].c = -c;
e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;
}
bool spfa()
{
for(int i=1; i<=n; i++) dis[i] = -INF;
int head = 1,tail = 2; que[1] = s; dis[s] = 0.0; inq[s] = true;
while(head!=tail)
{
int u = que[head]; head++; if(head>n+1) head = 1;
for(int i=fe[u]; i; i=e[i].nxt)
{
if(dis[e[i].v]<dis[u]+e[i].c-EPS && e[i].w>0)
{
dis[e[i].v] = dis[u]+e[i].c;
lst[e[i].v] = i;
if(!inq[e[i].v])
{
que[tail] = e[i].v; tail++; if(tail>n+1) tail = 1;
inq[e[i].v] = true;
}
}
}
inq[u] = false;
}
return dis[t]>-INF+1;
}
void calc_mfmc()
{
int flow = 100;
for(int i=t; i!=s; i=e[lst[i]].u) {flow = min(flow,e[lst[i]].w);}
for(int i=t; i!=s; i=e[lst[i]].u) {e[lst[i]].w -= flow; e[e[lst[i]].rev].w += flow;}
mf += flow; mc += dis[t]*(double)flow;
}
void mfmc(int _n,int _s,int _t)
{
n = _n; s = _s; t = _t;
while(spfa())
{
calc_mfmc();
}
// printf("mf=%d mc=%lf
",mf,mc);
}
}
using MaxFlowMinCost::fe;
using MaxFlowMinCost::e;
const int N = 100;
int a[N+3][N+3],b[N+3][N+3];
int n;
int main()
{
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]);
double mid = 0.0,ans = 1.0;
while(abs(ans-mid)>EPS)
{
mid = ans;
// printf("mid=%lf ans=%lf
",mid,ans);
for(int i=1; i<=n; i++) {MaxFlowMinCost::addedge(1,i+2,1,0.0);}
for(int i=1; i<=n; i++) {MaxFlowMinCost::addedge(i+n+2,2,1,0.0);}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
MaxFlowMinCost::addedge(i+2,j+n+2,1,a[i][j]-b[i][j]*mid);
}
}
MaxFlowMinCost::mfmc(n+n+2,1,2);
double deno = 0.0,nume = 0.0;
for(int i=3; i<=n+2; i++)
{
for(int j=fe[i]; j; j=e[j].nxt)
{
if(e[j].w==0)
{
int x = i-2,y = e[j].v-n-2;
// printf("(%d %d)
",x,y);
nume += a[x][y]; deno += b[x][y];
break;
}
}
}
ans = nume/deno;
MaxFlowMinCost::clear();
}
printf("%.6lf
",ans);
return 0;
}