# 网络流24题之十七 运输问题

2 3
220 280
170 120 210
77 39 105
150 186 122

48500
69140

1、从S向每个Xi连一条容量为仓库中货物数量ai，费用为0的有向边。
2、从每个Yi向T连一条容量为商店所需货物数量bi，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <iostream>
#define M 50000
#define N 500
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
map <string,int>ma;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
e[++tot].to=y;
e[tot].from=x;
e[tot].flow=z;
e[tot].cost=zz;
e[tot].next=st[x];
st[x]=tot;
}
queue<int>que;
bool spfa(int S,int T)
{
for (int i=S;i<=T;i++)
dis[i]=-INF;
memset(vis,0,sizeof vis);
que.push(S),vis[S]=1,dis[S]=0;
while(!que.empty())
{
int now=que.front();que.pop();vis[now]=0;
for (int i=st[now];~i;i=e[i].next)
if (e[i].flow>0 && dis[e[i].to]<dis[now]+e[i].cost)
{
dis[e[i].to]=dis[now]+e[i].cost;
pe[e[i].to]=i,pv[e[i].to]=now;
if (!vis[e[i].to])
vis[e[i].to]=1,que.push(e[i].to);
}
}
return dis[T]!=-INF;
}
Pair mfmc(int S,int T)
{
int COST=0,FLOW=0,flow;
while(spfa(S,T))
{
flow=0x3f3f3f3f;
for (int i=T;i!=S;i=pv[i])
flow=min(flow,e[pe[i]].flow);
COST+=flow*dis[T];
FLOW+=flow;
for (int i=T;i!=S;i=pv[i])
e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
}
return make_pair(FLOW,COST);
}
bool minspfa(int S,int T)
{
memset(dis,0x33,sizeof dis);
memset(vis,0,sizeof vis);
que.push(S),vis[S]=1,dis[S]=0;
while(!que.empty())
{
int now=que.front();que.pop();vis[now]=0;
for (int i=st[now];~i;i=e[i].next)
if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].cost)
{
dis[e[i].to]=dis[now]+e[i].cost;
pe[e[i].to]=i,pv[e[i].to]=now;
if (!vis[e[i].to])
vis[e[i].to]=1,que.push(e[i].to);
}
}
return dis[T]<INF;
}
Pair minfmc(int S,int T)
{
int COST=0,FLOW=0,flow;
while(minspfa(S,T))
{
flow=INF;
for (int i=T;i!=S;i=pv[i])
flow=min(flow,e[pe[i]].flow);
COST+=flow*dis[T];
FLOW+=flow;
for (int i=T;i!=S;i=pv[i])
e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;

return make_pair(FLOW,COST);
}
main()
{
int m,from,to,a[N],b[N],cost[N][N];
scanf("%d%d",&m,&n);
memset(e,-1,sizeof e);
memset(st,-1,sizeof st);
int S=0,T=n+m+1;
for (int i=1;i<=m;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
scanf("%d",&b[i]);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
for (int i=1;i<=m;i++)
for (int i=1;i<=n;i++)
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
Pair ans=minfmc(S,T);
printf("%d\n",ans.second);
memset(e,-1,sizeof e);
memset(st,-1,sizeof st);
for (int i=1;i<=m;i++)
}