题目：洛谷P4015、codevs1914。
题目大意：有n个仓库和m个商店，每个仓库存有不同的货物，每个商店需要不同的货物。
现在商店与仓库之间都有通道，可以供应的货物数量不限。
但每个仓库运往每个商店1个货物的费用不同。
现在问你最小的费用使得每个商店都能满足需求。
供货量等于收货量，且数据保证正确。
解题思路：最小费用最大流。
首先建出二分图，然后建立超源和超汇，则此题就变为最小费用最大流的裸题了。
第一问，求费用即可。
第二问，把边的费用取相反数，然后费用流过程一个字节不用改，再跑一边，最后费用取相反数即可。
C++ Code：
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
std::queue<int>q;
int n,m,cnt=-1,pre_e[255],head[255],d[255],a[255];
bool vis[255];
struct edge{
int from,to,cap,dis,nxt;
}e[300005],ee[300005];
inline int addedge(int u,int v,int cap,int dis){
e[++cnt]=(edge){u,v,cap,dis,head[u]};
ee[cnt]=(edge){u,v,cap,-dis,head[u]};
head[u]=cnt;
e[++cnt]=(edge){v,u,0,-dis,head[v]};
ee[cnt]=(edge){v,u,0,dis,head[v]};
head[v]=cnt;
}
bool maxflow(int s,int t,int& flow,int& cost){
memset(d,0x3f,sizeof d);
memset(a,0x3f,sizeof a);
memset(vis,0,sizeof vis);
memset(pre_e,0,sizeof pre_e);
d[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt)
if(e[i].cap&&d[e[i].to]>d[u]+e[i].dis){
d[e[i].to]=d[u]+e[i].dis;
a[e[i].to]=(a[u]>e[i].cap)?e[i].cap:a[u];
pre_e[e[i].to]=i;
if(!vis[e[i].to]){
vis[e[i].to]=true;
q.push(e[i].to);
}
}
}
if(d[t]==inf)return 0;
flow+=a[t];
cost+=a[t]*d[t];
for(int i=t;i!=s;i=e[pre_e[i]].from){
e[pre_e[i]].cap-=a[t];
e[pre_e[i]^1].cap+=a[t];
}
return 1;
}
int mincost(int s,int t){
int flow=0,cost=0;
while(maxflow(s,t,flow,cost));
return cost;
}
int main(){
memset(head,-1,sizeof head);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
addedge(0,i,x,0);
}
for(int i=1;i<=m;++i){
int x;
scanf("%d",&x);
addedge(i+n,n+m+1,x,0);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
int x;
scanf("%d",&x);
addedge(i,j+n,inf,x);
}
printf("%d
",mincost(0,n+m+1));
memcpy(e,ee,sizeof e);
printf("%d
",-mincost(0,n+m+1));
return 0;
}