传送门
费用流入门题。
直接按照题意模拟。
把货物的数量当做容量建边。
然后跑一次最小费用流和最大费用流就行了。
代码:
#include<bits/stdc++.h>
#define N 305
#define M 90005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m;
struct edge{int v,next,c,w;};
struct MCMF{
int first[N],d[N],pos[N],pred[N],flow[N],cnt,s,t;
bool in[N];
edge e[M];
inline void init(){memset(first,-1,sizeof(first)),cnt=-1,s=0,t=n+m+1;}
inline void addedge(int u,int v,int c,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}
inline void add(int u,int v,int c,int w){addedge(u,v,c,w),addedge(v,u,0,-w);}
inline bool spfa1(){
queue<int>q;
for(int i=1;i<=t;++i)d[i]=0x3f3f3f3f;
d[s]=0,flow[s]=0x3f3f3f3f,pred[t]=-1,in[s]=1,q.push(s);
while(!q.empty()){
int x=q.front();
q.pop(),in[x]=0;
for(int i=first[x];~i;i=e[i].next){
int v=e[i].v;
if(e[i].c&&d[v]>d[x]+e[i].w){
d[v]=d[x]+e[i].w,flow[v]=min(flow[x],e[i].c),pred[v]=x,pos[v]=i;
if(!in[v])in[v]=1,q.push(v);
}
}
}
return d[t]!=0x3f3f3f3f;
}
inline bool spfa2(){
queue<int>q;
for(int i=1;i<=t;++i)d[i]=-0x3f3f3f3f;
d[s]=0,flow[s]=0x3f3f3f3f,pred[t]=-1,in[s]=1,q.push(s);
while(!q.empty()){
int x=q.front();
q.pop(),in[x]=0;
for(int i=first[x];~i;i=e[i].next){
int v=e[i].v;
if(e[i].c&&d[v]<d[x]+e[i].w){
d[v]=d[x]+e[i].w,flow[v]=min(flow[x],e[i].c),pred[v]=x,pos[v]=i;
if(!in[v])in[v]=1,q.push(v);
}
}
}
return d[t]!=-0x3f3f3f3f;
}
inline int solve1(){
int ret=0;
for(int w=t;spfa1();w=t){
ret+=d[t]*flow[t];
while(w!=s)e[pos[w]].c-=flow[t],e[pos[w]^1].c+=flow[t],w=pred[w];
}
return ret;
}
inline int solve2(){
int ret=0;
for(int w=t;spfa2();w=t){
ret+=d[t]*flow[t];
while(w!=s)e[pos[w]].c-=flow[t],e[pos[w]^1].c+=flow[t],w=pred[w];
}
return ret;
}
}mcmf1,mcmf2;
int main(){
m=read(),n=read(),mcmf1.init(),mcmf2.init();
for(int i=1,val;i<=m;++i)val=read(),mcmf1.add(mcmf1.s,i,val,0),mcmf2.add(mcmf2.s,i,val,0);
for(int i=1,val;i<=n;++i)val=read(),mcmf1.add(i+m,mcmf1.t,val,0),mcmf2.add(i+m,mcmf2.t,val,0);
for(int i=1,val;i<=m;++i)for(int j=1;j<=n;++j)val=read(),mcmf1.add(i,j+m,0x3f3f3f3f,val),mcmf2.add(i,j+m,0x3f3f3f3f,val);
printf("%d\n%d",mcmf1.solve1(),mcmf2.solve2());
return 0;
}