传送门
无源汇最大费用可行流：
在推线性规划之前，先来看一个东西，无源汇最大费用可行流，也可称为最大费用循环流。
这玩意怎么求解，考虑我们实际上是用了若干环来覆盖原图。如果一个点在环上那么其入流等于出流。
我们先贪心把所有正权边选上，将其转化为一条负权边，记录一下每个点当前的流量差是多少。然后我们用负权边来把所有点的流量补齐，这样就是最小费用最大流了，实际上一定满流，也就是说最大流流量是确定了的，自己手推一下就行了。
最大费用循环流的线性规划模型为：
l
i
m
i
t
s
:
f
i
,
j
≤
c
a
p
i
,
j
−
f
i
,
j
≤
0
∀
v
,
∑
u
f
u
,
v
−
∑
u
f
v
,
u
≤
0
∀
v
,
∑
u
f
v
,
u
−
∑
u
f
u
,
v
≤
0
（其实这两条就是流量守恒）
m
a
x
i
m
i
z
e
:
∑
f
u
,
v
×
c
o
s
t
u
,
v
\begin{aligned} limits:&&&&&f_{i,j}\leq cap_{i,j}\\ &&&&&-f_{i,j}\leq 0\\ &&&&&\forall v,\sum_{u}f_{u,v}-\sum_{u}f_{v,u}\leq 0\\ &&&&&\forall v,\sum_{u}f_{v,u}-\sum_{u}f_{u,v}\leq 0 \text{（其实这两条就是流量守恒）}\\ maximize :&&&&&\sum f_{u,v}\times cost_{u,v} \end{aligned}
l
i
m
i
t
s
:
m
a
x
i
m
i
z
e
:
f
i
,
j
≤
c
a
p
i
,
j
−
f
i
,
j
≤
0
∀
v
,
u
∑
f
u
,
v
−
u
∑
f
v
,
u
≤
0
∀
v
,
u
∑
f
v
,
u
−
u
∑
f
u
,
v
≤
0
（其实这两条就是流量守恒）
∑
f
u
,
v
×
c
o
s
t
u
,
v
当然有重边的话也是允许的，不过需要再把上面的模型细化一下。
对偶一下可以转化为：
l
i
m
i
t
s
:
ϕ
i
−
ϕ
j
+
v
i
,
j
≥
c
o
s
t
i
,
j
m
i
n
i
m
i
z
e
:
∑
v
i
,
j
×
c
a
p
i
,
j
\begin{aligned} limits:&&&&&\phi_{i}-\phi_j+v_{i,j}\geq cost_{i,j}\\ minimize:&&&&&\sum v_{i,j}\times cap_{i,j} \end{aligned}
l
i
m
i
t
s
:
m
i
n
i
m
i
z
e
:
ϕ
i
−
ϕ
j
+
v
i
,
j
≥
c
o
s
t
i
,
j
∑
v
i
,
j
×
c
a
p
i
,
j
题解：
首先对于这道题，我们可以先二分出一个答案
λ
\lambda
λ
，然后看一下在达到这个要求的时候至少要用多少钱。
为了方便，我们设置两种超级植物，
s
,
t
s,t
s
,
t
，其中
s
s
s
必须在所有植物开始生长之前生长，
t
t
t
必须在所有植物开始生长之后生长。
然后看这道题的线性规划的式子，设
x
i
x_i
x
i
表示这个植物的开始生长时间，
y
i
y_i
y
i
表示这个植物的结束生长时间，
t
i
t_i
t
i
表示原来需要划分的时间，
d
i
d_i
d
i
表示氪金减少的时间：
l
i
m
i
t
s
:
y
s
+
λ
≥
x
t
x
i
≤
y
i
x
i
+
t
i
−
d
i
≤
y
i
x
i
+
t
i
−
d
i
≥
y
i
（其实这条不用考虑，最优化自然满足）
∀
(
u
,
v
)
∈
E
,
y
v
≤
x
u
m
i
n
i
m
i
z
e
:
∑
i
d
i
c
i
\begin{aligned} limits:&&&&&y_s+\lambda \geq x_t\\ &&&&&x_i\leq y_i\\ &&&&&x_i+t_i-d_i\leq y_i\\ &&&&&x_i+t_i-d_i\geq y_i \text{（其实这条不用考虑，最优化自然满足）}\\ &&&&&\forall (u,v)\in E,y_v\leq x_u\\ minimize :&&&&&\sum _{i}d_ic_i \end{aligned}
l
i
m
i
t
s
:
m
i
n
i
m
i
z
e
:
y
s
+
λ
≥
x
t
x
i
≤
y
i
x
i
+
t
i
−
d
i
≤
y
i
x
i
+
t
i
−
d
i
≥
y
i
（其实这条不用考虑，最优化自然满足）
∀
(
u
,
v
)
∈
E
,
y
v
≤
x
u
i
∑
d
i
c
i
发现好像可以直接套到上面的对偶问题里面：
l
i
m
i
t
s
:
y
s
−
x
t
+
λ
≥
0
y
i
−
x
i
+
0
≥
0
y
i
−
x
i
+
d
i
≥
t
i
∀
(
u
,
v
)
∈
E
,
x
u
−
y
v
+
0
≥
0
m
i
n
i
m
i
z
e
:
∑
d
i
c
i
\begin{aligned} limits : &&&&&y_s-x_t+\lambda \geq 0\\ &&&&&y_i-x_i+0\geq 0\\ &&&&&y_i-x_i+d_i\geq t_i\\ &&&&&\forall (u,v)\in E,x_u-y_v+0\geq 0\\ minimize:&&&&&\sum d_ic_i \end{aligned}
l
i
m
i
t
s
:
m
i
n
i
m
i
z
e
:
y
s
−
x
t
+
λ
≥
0
y
i
−
x
i
+
0
≥
0
y
i
−
x
i
+
d
i
≥
t
i
∀
(
u
,
v
)
∈
E
,
x
u
−
y
v
+
0
≥
0
∑
d
i
c
i
这个形式已经是最大费用循环流的对偶形式了，可以直接对应过去连边，但是注意到我们对于一些变量强制为0，其实因为在对偶问题里面是最小化，并且它的系数是非负的容量上界，直接把容量设置为INF就行了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const
using std::string;
class Farmville{
private:
static cs int N=1e3+7,M=55,INF=0x3f3f3f3f;
int S,T,tot,n,x[N],y[N];
int st[N],ed[N],flow[N],cost[N],ecnt;
inline void push(int u,int v,int f,int c){
st[++ecnt]=u,ed[ecnt]=v,flow[ecnt]=f,cost[ecnt]=c;
}
struct edge{int to,rev;ll cap;int w;};
typedef std::vector<edge>::iterator iter;
std::vector<edge> G[N];iter cur[N];
inline void adde(int u,int v,ll cap,int cost){
G[u].push_back((edge){v,G[v].size(),cap,cost});
G[v].push_back((edge){u,G[u].size()-1,0,-cost});
}
int dis[N];bool vis[N];
inline bool SPFA(){
memset(dis+1,0x3f,sizeof(int)*tot);
memset(vis+1,0,sizeof(bool)*tot);
std::deque<int> q(1,S);dis[S]=0;
while(!q.empty()){
int u=q.front();q.pop_front();
vis[u]=false;cur[u]=G[u].begin();
for(auto e:G[u])if(e.cap&&dis[e.to]>dis[u]+e.w){
dis[e.to]=dis[u]+e.w;
if(!vis[e.to]){
if(!q.empty()&&dis[e.to]<=dis[q.front()])q.push_front(e.to);
else q.push_back(e.to);
vis[e.to]=true;
}
}
}
return dis[T]<INF;
}
ll tot_flow;ll tot_cost;
ll dfs(int u,ll flow){
if(u==T){
tot_flow+=flow;
tot_cost+=flow*dis[T];
return flow;
}
vis[u]=true;ll ans=0;
for(iter &e=cur[u];e!=G[u].end();++e)
if(e->cap&&!vis[e->to]&&dis[e->to]==dis[u]+e->w){
ll delta=dfs(e->to,std::min(flow-ans,e->cap));
if(!delta){vis[e->to]=true;continue;}
e->cap-=delta;G[e->to][e->rev].cap+=delta;
if((ans+=delta)==flow)break;
}
vis[u]=false;return ans;
}
ll d[N];
inline bool check(int budget){
for(int re i=1;i<=tot;++i)G[i].clear(),d[i]=0;
ll sum=0;
for(int re i=1;i<=ecnt;++i){
int u=st[i],v=ed[i],f=flow[i],c=cost[i];
if(c<0)adde(u,v,f,-c);
else {
sum+=(ll)f*c;
d[u]+=f,d[v]-=f;
adde(v,u,f,c);
}
}
for(int re i=1;i<=tot;++i)if(i!=S&&i!=T){
if(d[i]<0)adde(S,i,-d[i],0);
else adde(i,T,d[i],0);
}
tot_cost=tot_flow=0;
while(SPFA())dfs(S,1ll<<60);
return sum-tot_cost>budget;
}
public:
Farmville(){}
int minTime(std::vector<string> s,std::vector<int> t,
std::vector<int> c,int budget){
n=t.size();S=1,T=tot=2;int ys=++tot,xt=++tot;
for(int re i=0;i<n;++i)x[i]=++tot,y[i]=++tot;
for(int re i=0;i<n;++i){
push(ys,x[i],INF,0);
push(y[i],xt,INF,0);
push(x[i],y[i],INF,0);
push(x[i],y[i],c[i],t[i]);
}
for(int re i=0;i<n;++i)
for(int re j=0;j<n;++j)
if(s[i][j]=='1')push(y[j],x[i],INF,0);
push(xt,ys,INF,0);
int l=0,r=100000,ans;
while(l<=r){
int m=l+r>>1;
cost[ecnt]=-m;
if(check(budget))l=m+1;
else ans=m,r=m-1;
}
return ans;
}
};
#ifdef zxyoi
Farmville Solver;
signed main(){
std::cout<<Solver.minTime(
{"000","100","110"},
{3,18,1},
{242949,8471,54403957},
53867
)<<'\n';
return 0;
}
#endif