为什么感觉你的EK那么诡异呢?
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=105,MAX_V=205,MAX_M=MAX_N*MAX_N+2*MAX_N;
const int INF=0x3f3f3f3f;
namespace max_flow
{
int head[MAX_V],tp[MAX_V],dis[MAX_V],cnt,pre[MAX_V],last[MAX_V];
bool used[MAX_V];
int max_flow;
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
}
struct Edge
{
int v,cap,cost,nxt;
Edge(){}
Edge(int _v,int _cap,int _cost,int _nxt)
{
v=_v;
cap=_cap;
cost=_cost;
nxt=_nxt;
}
};
Edge E[MAX_M<<1];
void addedge(int u,int v,int cap,int cost)
{
E[cnt]=Edge(v,cap,cost,head[u]);
head[u]=cnt++;
}
void add_edge(int u,int v,int cap,int cost)
{
addedge(u,v,cap,cost);
addedge(v,u,0,-cost);
}
bool SPFA(int s,int t)
{
memset(dis,0x3f,sizeof(dis));
queue<int> q;
dis[s]=0;
used[s]=true;
q.push(s);
while(!q.empty())
{
int v=q.front();
q.pop();
for(int i=head[v];i!=-1;i=E[i].nxt)
{
int to=E[i].v,w=E[i].cost;
if(E[i].cap>0 && dis[to]>dis[v]+w)
{
dis[to]=dis[v]+w;
pre[to]=i;
last[to]=v;
if(!used[to])
{
used[to]=true;
q.push(to);
}
}
}
used[v]=false;
}
return dis[t]<INF;
}
int min_cost_flow(int s,int t)
{
int ret=0;
while(SPFA(s,t))
{
int flow=INF;
for(int i=t;i!=s;i=last[i])flow=min(flow,E[pre[i]].cap);
for(int i=t;i!=s;i=last[i])
{
E[pre[i]].cap-=flow;
E[pre[i]^1].cap+=flow;
}
ret+=flow*dis[t];
max_flow+=flow;
}
return ret;
}
}
int n,m,A[MAX_N],B[MAX_N],C[MAX_N][MAX_N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>A[i];
for(int i=1;i<=m;i++)cin>>B[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>C[i][j];
}
}
int s=0,t=n+m+1;
max_flow::init();
for(int i=1;i<=n;i++)max_flow::add_edge(s,i,A[i],0);
for(int i=1;i<=m;i++)max_flow::add_edge(i+n,t,B[i],0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
max_flow::add_edge(i,j+n,INF,C[i][j]);
}
}
cout<<max_flow::min_cost_flow(s,t)<<endl;
max_flow::init();
for(int i=1;i<=n;i++)max_flow::add_edge(s,i,A[i],0);
for(int i=1;i<=m;i++)max_flow::add_edge(i+n,t,B[i],0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
max_flow::add_edge(i,j+n,INF,-C[i][j]);
}
}
cout<<-max_flow::min_cost_flow(s,t)<<endl;
return 0;
}
```
by Smile_Cindy @ 2020-07-21 11:46:31
@[Alpha](/user/87058) /委屈,qwq
by JK_LOVER @ 2020-07-21 11:50:15