前言
分数规划是来求一个分式的极值
形象点就是已知 \(a_i,b_i\) 求
\[\frac{\sum_{i=1}^n a_i \times x_i}{\sum_{i=1}^n b_i \times x_i}
\]
的极值，其中 \(x_i\in \{0,1\}\)
显然可以二分求解，设当前二分值为 \(mid\)
若 \(mid\) 有解 ，则有
\[\sum_{i=1}^n a_i \times x_i \geq mid \times \sum_{i=1}^n b_i \times x_i
\]
即
\[\sum_{i=1}^n a_i \times x_i - mid \times \sum_{i=1}^n b_i \times x_i \geq 0
\]
\[\sum_{i=1}^n (a_i-b_i\times mid) \times x_i \geq 0
\]
前置知识
二分
CF1486D Max Median
二分练手题，与分数规划无关
给定一个长度为 \(n\) 的序列 \(a\)，求所有长度 \(\ge k\) 的连续子序列中，中位数的最大值。定义中位数是一个长度为 \(x\) 的序列升序排序后的第 \(\left\lfloor\frac{x+1}{2}\right\rfloor\) 位的值。
因为答案具有单调性，所以考虑二分
设二分值为 \(mid\)
可以构造序列 \(b\) 其中 \(b_i= (a_i \ge mid)\)
\(mid\) 可以作为答案当且仅当有序列 \([l,r]\) 满足
\(\sum_{i=l}^r b_i > 0\) 且 \(r-l+1\ge k\)
前缀和再前缀 \(min\) 一下就行
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
ll n,k,ls,rs,a[200020],b[210000];
inline bool check(ll mid){
rep(i,1,n) b[i]=(a[i]>=mid?1:-1),b[i]+=b[i-1];
ll mx=0,ip=0;
rep(i,k,n){
if(b[i]-mx>0) {
ls=ip+1;
rs=i;
return 1;
}
if(mx>b[i-k+1])
mx=min(b[i-k+1],mx),ip=i-k+1;
}
return 0;
}
int main(){
n=in(); k=in();
rep(i,1,n) a[i]=in();
ll l=-1e9,r=1e9,mid,ans=1e9;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
check(ans);
// cout<<ans<<' '<<ls<<' '<<rs<<'\n';
sort(a+ls,a+rs+1);
cout<<ans;
return 0;
}
代码有点乱，见谅
01分数规划
没找到原题，bzoj有，链接不给了
求
\[\frac{\sum_{i=1}^n a_i \times x_i}{\sum_{i=1}^n b_i \times x_i}
\]
的最大值，其中 \(x_i\in \{0,1\}\)
并且满足 \(\sum x_i = k\)
先二分 \(mid\) ，然后因为要
\[\sum_{i=1}^n (a_i-b_i\times mid) \times x_i \geq 0
\]
所以贪心选 \((a_i-b_i\times mid)\) 前 \(k\) 大就行了
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
ll n,k;
double a[200020],b[210000];
inline bool check(double mid){
vector<double> vec; double v=0; vec.clear();
rep(i,1,n) vec.pb(a[i]-b[i]*mid);
sort(vec.begin(),vec.end(),greater<>());
rep(i,0,k-1) v+=vec[i];
return v>=1e-5;
}
int main(){
n=in(); k=in();
rep(i,1,n) sf("%lf",&a[i]);
rep(i,1,n) sf("%lf",&b[i]);
double l=-1e9,r=1e9,mid,ans=1e9;
while((r-l)>1e-9){
mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid;
else r=mid;
}
pf("%.4lf\n",ans);
return 0;
}
[ABC236E] Average and Median
\(n\) 个数 \(a_{1}\dots a_n\) 排成一列。现在要选出一些数，满足 任意两个相邻的数中至少有一个数被选择。
请求出：
-
所有选择方案中，被选中的数字平均值的最大值，误差在 \(10^{-3}\) 以内视为正确；
-
所有选择方案中，被选中的数字中位数的的最大值。在这里，偶数 \(2k\) 个数的中位数视作第 \(k\) 小的数。
01规划很难弄，于是写了个二分套 DP
求最大平均值和最大中位数
对于最大平均值可以构造 \(b_i=a_i-mid\)
然后 \(dp[i][0]\) 代表不选 \(b[i]\) 的最大值
\(dp[i][1]\) 代表选 \(b[i]\) 的最大值
则
\[dp[i][0]=dp[i-1][1]
\]
\[dp[i][1]=max(dp[i-1][0],dp[i-1][1])+b[i]
\]
判断 \(max(dp[n][0],dp[n][1]) >=0\) 即可
求最大中位数，一样的套路
可以构造 \(b_i=(a_i \ge mid)\)
然后 \(dp[i][0]\) 代表不选 \(b[i]\) 的最大值
\(dp[i][1]\) 代表选 \(b[i]\) 的最大值
则
\[dp[i][0]=dp[i-1][1]
\]
\[dp[i][1]=max(dp[i-1][0],dp[i-1][1])+b[i]
\]
判断 \(max(dp[n][0],dp[n][1]) >=0\) 即可
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
ll n,k;
ll a[200020],c[200020],f[200020][2];
double b[210000],dp[200020][2];
inline bool check(double mid){
rep(i,1,n) b[i]=a[i]-mid;
dp[1][1]=b[1]; dp[1][0]=0;
rep(i,2,n){
dp[i][1]=max(dp[i-1][0],dp[i-1][1])+b[i];
dp[i][0]=dp[i-1][1];
}
double v=max(dp[n][0],dp[n][1]);
return v>=0;
}
inline bool chk(ll v){
rep(i,1,n) c[i]=(a[i]>=v?1:-1);
ll mi=0;
f[1][1]=c[1]; f[1][0]=0;
rep(i,2,n){
f[i][1]=max(f[i-1][1],f[i-1][0])+c[i];
f[i][0]=f[i-1][1];
if(i==n&&max(f[i][1],f[i][0])>0) return 1;
}
return 0;
}
inline void sol(){
ll l=-1e9,r=1e9,mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(chk(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
pf("%lld\n",ans);
}
int main(){
n=in();
rep(i,1,n) sf("%lld",&a[i]);
double l=-1e9,r=1e9,mid,ans=1e9;
while((r-l>=1e-6)){
mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid;
else r=mid;
}
pf("%.4lf\n",ans);
sol();
return 0;
}
P4377 [USACO18OPEN] Talent Show G
简化题意就是求
求
\[\frac{\sum_{i=1}^n a_i \times x_i}{\sum_{i=1}^n b_i \times x_i}
\]
的最大值，其中 \(x_i\in \{0,1\}\)
多了个额外条件
\(\sum b_i \times x_i \ge W\)
数据范围
$n\leq250 $ , \(0 \leq b_i \leq 10^6\) , \(W \leq 1000\)
分数规划套01背包
二分出 \(mid\)
先构造 \(c_i=a_i-mid\times b_i\)
显然是求体积 \(b_i\) 价值 \(c_i\) 的背包
但 \(0 \leq b_i \leq 10^6\) ，需要优化
注意到我们答案是取 \(max_{i=W}^{\infty} f_i\)
而 \(i>W\) 其实都可以存在 \(i=W\) 的状态，相当于体积与 \(W\) 取 \(min\) ，最后判断 \(f_w \ge 0\) 即可
最终复杂度 \(O(nW \log V)\)
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
ll n,v,w[5050],t[5050];
double c[5050],dp[50050];
inline bool check(double mid){
rep(i,1,n) c[i]=1.0*t[i]-w[i]*mid;
rep(i,1,3000) dp[i]=-1e18;
rep(i,1,n){
drep(j,v,0){
ll sz=min(w[i]+j,v);
dp[sz]=max(dp[sz],dp[j]+c[i]);
}
}
double ret=dp[v];
return ret>=0;
}
int main(){
n=in(); v=in();
rep(i,1,n) w[i]=in(),t[i]=in();
double l=-1e6,r=1e6,mid,ans=0;
while(r-l>=1e-8){
mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid;
else r=mid;
}
ll an=ans*1000;
cout<<an;
return 0;
}
P4322 [JSOI2016] 最佳团体
分数规划套树上背包
简要题意，一颗以 \(0\) 为根的数，如果选择 \(i\) ，则必须选择它的父节点 \(fa_i\) ，每个节点有值 \(s_i,p_i\) ,一共只恰好选 \(k\) 个点，求
\[\frac{\sum p_i}{\sum s_i}
\]
的最大值
分数规划
其实原题题意是很多棵树（森林），但有做选课那道题的经验，可以直接建一个超级根 \(0\)
然后二分 \(mid\) ，令 \(c_i=p_i-mid\times s_i\)
做树上背包， \(dp[i][j]\) 代表以 \(i\) 为根选 \(j\) 个点的最大 \(c\) 值和
注意如果 \(dp\) 没写好，转移会成为 \(n^3\) 的复杂度
至于复杂度为什么是 \(n^2\) ，因为最多只会在 \(lca\) 处合并一次，一共有 \(n^2\) 对 \(lca\) ，所以复杂度 \(n^2\)
我的实现比较奇怪，是先把儿子的值做背包，再加上当前节点的值
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
int n,k,sz[2505],s[2505],p[2505];
double mid,ans,c[2505],dp[2505][2505];
vector<int> e[2505];
void dfs(int u){
sz[u]=1; c[u]=1.0*p[u]-mid*s[u];
for(int v:e[u]){
dfs(v);
sz[u]+=sz[v];
}
rep(i,1,sz[u]) dp[u][i]=-1e8;
int now=0;
for(int v:e[u]){
now+=sz[v];
drep(i,now,0){
drep(j,min(sz[v],i),1){
dp[u][i]=max(dp[u][i],dp[v][j]+dp[u][i-j]);
}
}
}
if(u)
drep(i,sz[u],1) dp[u][i]=dp[u][i-1]+c[u];
}
int main(){
k=in(); n=in();
rep(i,1,n){
s[i]=in();
p[i]=in();
int fa=in();
e[fa].pb(i);
}
double l=-1e9,r=1e9;
while((r-l)>1e-6){
mid=(l+r)/2;
dfs(0); bool ck=0;
ck=(dp[0][k]>=0);
// pf("mid: %.3lf %.3lf \n",mid,dp[0][k]);
if(ck) l=mid,ans=mid;
else r=mid;
}
pf("%.3lf\n",ans);
return 0;
}
P3199 [HNOI2009] 最小圈
求有向图边权平均值最小的环
分数规划求最小均值环
还是二分 \(mid\) (((
然后我们把边权全部减去 \(mid\) ，有一个特别的结论
就是如果有负环，那么就说明有解 （很显然但是很有意思）
还有要注意的点, 直接 spfa 很容易跑满 \(nm\) 的复杂度然后 \(TLE\)
我们需要使用 \(dfs\) 写法的 \(spfa\)
大概如下
bool spfa(int u){
vis[u]=1;
for(v:e[u]){
if(d[v]>d[u]+w-mid){
if(vis[v]) return true;
d[v]=d[u]+w-mid;
spfa(v);
}
}
vis[u]=0;
return false;
}
因为只用判负环，所以我们保证 \(d[u]<0\) 一直走就行
初始化所有 \(d[i]=0\)
然后就简单了
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
int n,m,ok;
bitset<3030> vis,cle;
double mid,ans,d[3030];
struct node{
int v;
double w;
};
vector<node> e[3030];
void check(int u){
if(ok) return;
vis[u]=1;
for(node o:e[u]){
int v=o.v;
if(d[v]>d[u]-mid+o.w){
if(vis[v]){
ok=1;
return;
}
d[v]=d[u]-mid+o.w;
check(v);
}
if(ok) return;
}
vis[u]=0;
}
int main(){
n=in(); m=in();
while(m--){
int u=in(),v=in();
double w;
sf("%lf",&w);
e[u].pb({v,w});
}
double l=-1e6,r=1e6;
while((r-l)>1e-10){
mid=(l+r)/2;
vis&=cle;
rep(i,1,n) d[i]=0; ok=0;
rep(i,1,n) check(i);
if(ok) ans=mid,r=mid;
else l=mid;
}
pf("%.8lf\n",l);
return 0;
}
P2868 [USACO07DEC] Sightseeing Cows G
一年前学最短路做过？但真没印象了
简要题意：求点权和除以边权和最大的简单环
跟最小圈那题差不多，只不过改了点
因为是个环，所以可以把点权转移到边上，则 \(w'_{u,v}=a_u-w_{u,v}\times mid\)
然后同样判断一下是否有负环即可
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
int n,m,ok;
bitset<3030> vis,cle;
double mid,ans,w[3030],d[3030];
struct node{
int v;
double w;
};
vector<node> e[3030];
void check(int u){
if(ok) return;
vis[u]=1;
for(node o:e[u]){
int v=o.v; double g=w[u]-o.w*mid;
if(d[v]>d[u]-g){
if(vis[v]){
ok=1;
return;
}
d[v]=d[u]-g;
check(v);
}
if(ok) return;
}
vis[u]=0;
}
int main(){
n=in(); m=in();
rep(i,1,n) w[i]=in();
while(m--){
int u=in(),v=in();
double w;
sf("%lf",&w);
e[u].pb({v,w});
}
double l=-1e6,r=1e6;
while((r-l)>1e-10){
mid=(l+r)/2;
vis&=cle;
rep(i,1,n) d[i]=0; ok=0;
rep(i,1,n) check(i);
if(ok) ans=mid,l=mid;
else r=mid;
}
pf("%.2lf\n",ans);
return 0;
}
P6087 [JSOI2015] 送礼物
分数规划使用单调队列优化决策
神仙题，调了很久（也就3h）
简要题意：求一个权值最大的区间 \([l,r]\)
满足 \(L \leq r-l+1 \leq R\)
并且 \(\Large \frac{\max_{i=l}^r a_i - \min_{i=l}^r a_i}{r-l+k}\) 最大
首选分数规划，但是发现 \(max-min\) 很难处理，所以要找些奇怪的性质：
当区间长度大于 \(L\) 时，\(max\) 和 \(min\) 分别在区间两端
为什么，贪心的想，本来你的决策长度为 \(L\) ,如果你扩张了区间长度，区间极值没有变化
所以分子的值没变，分母反而变大了，就不是最优的了。
然后我们分类讨论
-
\(a_r=max\) , \(a_l=min\)
所以 \(a_r-a_l \ge (r-l+k) \times mid\)
即 \(a_r-r\times mid -a_l + l\times mid \ge mid\)
单调队列维护 \(a_l-l\times mid\) 的最小值
-
\(a_r=min\) , \(a_l=max\)
所以 \(a_l-a_r \ge (r-l+k) \times mid\)
即 \(a_l+l\times mid -a_r - r\times mid \ge mid\)
单调队列维护 \(a_l+l\times mid\) 的最大值
会有很多不合法的情况，但是很明显推出来值不是最优的
然后考虑长度等于 \(L\) ，直接滑动窗口求最大值和最小值，取最大的一组解与长度大于 \(L\) 的取 \(max\) 即可
代码：
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
#define nx 50005
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
int T,n,k,L,R;
ll a[nx+5],q[nx+5],h,t,q2[nx+5],h2,t2;
/*
c[i]-c[j]>=(i-j+k)*mid
c[j]-c[i]>=(i-j+k)*mid
c[i]-i*mid-c[j]+j*mid>=k*mid
*/
double mid,ans,c[nx+5],c2[nx+5];
inline bool check(){
rep(i,1,n) c[i]=a[i]*1.0-mid*i,c2[i]=a[i]*1.0+mid*i;
h2=h=1,t=t2=0;
rep(i,L,n){
while(h<=t&&q[h]<i-R+1) ++h;
while(h2<=t2&&q2[h2]<i-R+1) ++h2;
while(h<=t&&c[q[t]]>c[i-L+1]) --t;
while(h2<=t2&&c2[q2[t2]]<c2[i-L+1]) --t2;
q2[++t2]=q[++t]=i-L+1;
// pf("now : l: %d r: %d %.3lf\n",q[h],i,(c[i]-c[q[h]]));
if(h<=t&&(c[i]-c[q[h]])>=mid*k) return true;
// pf("now : l: %d r: %d %.3lf\n",q2[h2],i,(c2[q2[h2]]-c2[i]));
if(h2<=t2&&(c2[q2[h2]]-c2[i])>=mid*k) return true;
}
// pf("debug false\n");
return false;
}
inline double sol(){
h2=h=1,t=t2=0;
double ret=0;
rep(i,1,n){
while(h<=t&&q[h]<i-L+1) ++h;
while(h2<=t2&&q2[h2]<i-L+1) ++h2;
while(h<=t&&a[q[t]]<a[i]) --t;
while(h2<=t2&&a[q2[t2]]>a[i]) --t2;
q[++t]=q2[++t2]=i;
ret=max(ret,(a[q[h]]-a[i])*1.0/(L-1+k));
ret=max(ret,(a[i]-a[q2[h2]])*1.0/(L-1+k));
}
return ret;
}
int main(){
T=in();
while(T--){
n=in(); k=in(); L=in(); R=in();
rep(i,1,n) a[i]=in();
double l=-1e6,r=1e6;
while((r-l)>1e-7){
mid=(l+r)/2;
if(check()) ans=mid,l=mid;
else r=mid;
// pf("-------debug-------\n");
}
pf("%.4lf\n",max(ans,sol()));
}
return 0;
}
P3705 [SDOI2017] 新生舞会
简要题意：
二分图最大匹配，且要有选择的边权值
\[\frac{\sum a_{u,v}}{\sum b_{u,v}}
\]
最小
都是套路题，先二分，把边权变成
\(c_{i,j}=a_{i.j}-mid\times b_{i.j}\)
然后发现这其实是求二分图最小权匹配是否大于 \(0\)
但因为数据范围比较大，所以考虑费用流求最大匹配
最后复杂度 \(O(n^3 \times \log V)\)
还有就是有人问是否存在正环，显然不行，因为网络流都是单向边，不会有环，唯一的反边构成的环也是 \(0\)
代码
#include<bits/stdc++.h>
#define ll long long
#define sf scanf
#define pf printf
#define pb push_back
#define cmax(x,y) x=max(x,y);
#define cmin(x,y) x=min(x,y);
#define ull unsigned long long
#define drep(i,x,y) for(int i=x;i>=y;i--)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define IOS ios::sync_with_stdio(false)
using namespace std;
inline ll in(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') (ch=='-'?f=-1:1),ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }
template<int T> struct Dinic{
struct edge{
int v,w,next;
double f;
}e[T*T+5];
int head[T+5],tot,now[T+5];
double d[T+5]; bool vis[T+5];
Dinic(){
tot=1;
for(int i=1;i<=T;i++) head[i]=0;
}
inline void clear(){
tot=1;
for(int i=1;i<=T;i++) head[i]=0;
}
inline void add(int x,int y,int c,double f){
e[++tot]={y,c,head[x],f};
head[x]=tot;
e[++tot]={x,0,head[y],-f};
head[y]=tot;
}
int inf=2e9;
inline int bfs(int s,int t){
for(int i=1;i<=T;i++) d[i]=1e18,vis[i]=0;
queue<int> q;
while(q.size()) q.pop();
d[s]=0; vis[s]=1; q.push(s); now[s]=head[s];
while(q.size()){
int u=q.front();
q.pop(); vis[u]=0;
for(int i=now[u];i;i=e[i].next){
int v=e[i].v;
if(e[i].w&&d[v]>d[u]+e[i].f){
d[v]=d[u]+e[i].f;
now[v]=head[v];
if(!vis[v]) vis[v]=1,q.push(v);
}
}
}
// pf("%.6lf\n",d[t]);
return d[t]<1e18;
}
double minf=0;
bool vi[T+5];
int dinic(int u,int flow,int t){
if(u==t) return flow;
int rest=flow,ret=0;
vi[u]=1;
for(int i=now[u];i&&rest;i=e[i].next){
int v=e[i].v;
now[u]=i;
if(e[i].w&&(d[v]==d[u]+e[i].f)&&!vi[v]){
int p=dinic(v,min(rest,e[i].w),t);
if(!p){
d[v]=0;
continue;
}
rest-=p;
ret+=p;
e[i].w-=p;
e[i^1].w+=p;
minf+=e[i].f*p;
}
}
vi[u]=0;
return ret;
}
inline int flow(int s,int t){
for(int i=1;i<=T;i++) now[i]=0;
minf=0;
int ret=0,w;
while(bfs(s,t)) {
while(1){
w=dinic(s,inf,t);
ret+=w;
if(!w) break;
}
}
return ret;
}
};
Dinic<205> S;
int n,a[105][105],b[105][105];
double mid,ans;
inline bool check(){
S.clear();
rep(i,1,n){
S.add(n*2+1,i,1,0);
S.add(i+n,n*2+2,1,0);
rep(j,1,n){
double f=mid*b[i][j]-1.0*a[i][j];
S.add(i,j+n,1,f);
}
}
if(S.flow(n*2+1,n*2+2)==n&&S.minf>0) return true;
return false;
}
int main(){
n=in();
rep(i,1,n) rep(j,1,n) a[i][j]=in();
rep(i,1,n) rep(j,1,n) b[i][j]=in();
double l=0,r=1e5;
while((r-l)>1e-8){
mid=(l+r)/2;
if(check()) ans=mid,r=mid;
else l=mid;
}
pf("%.6lf\n",ans);
return 0;
}
其实是第一次写费用流诶。
总结
一个不错的 \(trick\) ,挺有意思的题
后边继续更最小密度子图就彻底完结了！