最大费用最大流
- 最大求法：
- 将所有费用取反
- 求最小费用，再取反0
cpp
int h[N],e[M],f[M],w[M],ne[M],idx;
int dis[N],cur[N];//d表示最短距离,cur为当前弧
int n,m,S,T;
bool vis[N];
int height[N];// 势能函数
vector<int> dot;// 点数
void add(int a,int b,int c,int d){
e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool dijk(){
for(auto &i:dot)dis[i]=INF,cur[i]=h[i];
priority_queue<PII,vector<PII>,greater<>> pq;
dis[S]=0;
pq.emplace(0,S);
while(!pq.empty()){
auto [d,u]=pq.top();
pq.pop();
if(dis[u]!=d)continue;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(f[i]&&dis[v]>d+height[u]-height[v]+w[i]){
dis[v]=d+height[u]-height[v]+w[i];
pq.emplace(dis[v],v);
}
}
}
return dis[T]!=INF;
}
int find(int u,int limit){
if(!limit||u==T)return limit;
int flow=0;
vis[u]=1;
for(int &i=cur[u];~i&&flow<limit;i=ne[i]){
int v=e[i];
if(dis[v]==dis[u]+height[u]-height[v]+w[i]&&f[i]&&!vis[v]){
int t=find(v,min(f[i],limit-flow));
f[i]-=t,f[i^1]+=t,flow+=t;
if(flow==limit)break;
}
}
vis[u]=0;
return flow;
}
void mcmf(int &flow,int &cost){
flow=cost=0;
int r;
while(dijk()){
int r=find(S,INF);
flow+=r;
for(auto &i:dot)height[i]+=dis[i];
cost+=height[T]*r;
}
}
void solve(){
cin>>m>>n;
S=0,T=n+m+1;
for(int i=0;i<=n+m+1;i++)dot.push_back(i);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++){
int x;
cin>>x;
add(S,i,x,0);
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
add(m+i,T,x,0);
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
int c;
cin>>c;
add(i,m+j,INF,c);
}
}
int flow,cost;
mcmf(flow,cost);
cout<<cost<<"\n";
for(int i=0;i<idx;i+=2){
f[i]+=f[i^1],f[i^1]=0;
w[i]=-w[i],w[i^1]=-w[i^1];
}
mcmf(flow,cost);
cout<<-cost;
}