运输问题

很水的费用流，本弱都能想出来QwQ
就是建一个图
（但是我不会怎么操作一下可以不重建图所以直接暴力重建，反正数据小）
求最大费用最大流的时候，就把cost变成-cost，之后输出-mincost即可。
强啊！Orz
代码非常清楚

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
queue<int>q;
const int N=1005,S=0,T=405,inf=0x3f3f3f3f;
int m,n,dis[N],from[N],head[N],ecnt=1,a[N],b[N],c[N][N];
bool vis[N];
struct Edge{int to,nxt,val,cost,from;}e[N*N<<3];
void add(int bg,int ed,int val,int cost){e[++ecnt].cost=cost;e[ecnt].from=bg;e[ecnt].nxt=head[bg];e[ecnt].to=ed;e[ecnt].val=val;head[bg]=ecnt;e[++ecnt].cost=-cost;e[ecnt].from=ed;e[ecnt].nxt=head[ed];e[ecnt].to=bg;e[ecnt].val=0;head[ed]=ecnt;}
bool spfa() {
	M(dis,0x3f);
	M(vis,0);
	q.push(S);
	dis[S]=0;vis[S]=1;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].val){
				if(e[i].cost+dis[u]<dis[v]){
					dis[v]=e[i].cost+dis[u];from[v]=i;
					if(!vis[v]) vis[v]=1,q.push(v);
				}
			}	
		}
	}
	return dis[T]!=inf;
}
int mincost;
void mcf(){
	int i=from[T],mx=-inf,mn=inf;
	while(i){mx=max(mx,e[i].val),mn=min(e[i].val,mn);i=from[e[i].from];}
	i=from[T];
	while(i){e[i].val-=mn;e[i^1].val+=mn;mincost+=mn*e[i].cost;i=from[e[i].from];}
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x);a[i]=x;
		add(S,i,x,0);
	}
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);b[i]=x;
		add(i+m,T,x,0);
	}
	for(int i=1,x;i<=m;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&x);c[i][j]=x;
			add(i,j+m,inf,x);
		}
	}
	
	while(spfa())
	mcf();
	printf("%d
",mincost);
	M(head,0);ecnt=1;M(from,0);
	for(int i=1,x;i<=m;i++){
		x=a[i];
		add(S,i,x,0);
	}
	for(int i=1,x;i<=n;i++){
		x=b[i];
		add(i+m,T,x,0);
	}
	for(int i=1,x;i<=m;i++){
		for(int j=1;j<=n;j++){
			x=c[i][j];
			add(i,j+m,inf,-x);
		}
	}
	mincost=0;
	while(spfa()) mcf();
	cout<<-mincost;
}