题意：
思路：
【问题分析】
费用流问题。
【建模方法】
把所有仓库看做二分图中顶点Xi，所有零售商店看做二分图中顶点Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为仓库中货物数量ai，费用为0的有向边。
2、从每个Yi向T连一条容量为商店所需货物数量bi，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。
求最小费用最大流，最小费用流值就是最少运费，求最大费用最大流，最大费用流值就是最多运费。
【建模分析】
把每个仓库想象成一个中转站，由源点运来ai单位货物，运费为0，每个商店也为一个中转站，运向目标汇点bi单位货物。每个仓库和零售商店之间有一条道路，容量为无穷大，费用为单位运费cij。求从源
点到汇点的费用流，就是运费。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef long double ld; 7 typedef pair<int,int> PII; 8 typedef pair<ll,ll> Pll; 9 typedef vector<int> VI; 10 typedef vector<PII> VII; 11 typedef pair<ll,ll>P; 12 #define N 100010 13 #define M 1000000 14 #define INF 1e9 15 #define fi first 16 #define se second 17 #define MP make_pair 18 #define pb push_back 19 #define pi acos(-1) 20 #define mem(a,b) memset(a,b,sizeof(a)) 21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 23 #define lowbit(x) x&(-x) 24 #define Rand (rand()*(1<<16)+rand()) 25 #define id(x) ((x)<=B?(x):m-n/(x)+1) 26 #define ls p<<1 27 #define rs p<<1|1 28 29 const ll MOD=1e9+7,inv2=(MOD+1)/2; 30 double eps=1e-6; 31 int dx[4]={-1,1,0,0}; 32 int dy[4]={0,0,-1,1}; 33 34 int head[N],vet[N],len1[N],len2[N],nxt[N],dis[N],q[N],inq[N],a[N],b[N],c[500][500], 35 pre[N][2],s,S,T,tot,ans1,ans2,n,m; 36 37 38 39 int read() 40 { 41 int v=0,f=1; 42 char c=getchar(); 43 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 44 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 45 return v*f; 46 } 47 48 void add(int a,int b,int c,int d) 49 { 50 nxt[++tot]=head[a]; 51 vet[tot]=b; 52 len1[tot]=c; 53 len2[tot]=d; 54 head[a]=tot; 55 56 nxt[++tot]=head[b]; 57 vet[tot]=a; 58 len1[tot]=0; 59 len2[tot]=-d; 60 head[b]=tot; 61 } 62 63 void addedge() 64 { 65 tot=1; 66 rep(i,1,s) head[i]=0; 67 rep(i,1,n) add(S,i,a[i],0); 68 rep(i,1,m) add(i+n,T,b[i],0); 69 rep(i,1,n) 70 rep(j,1,m) add(i,j+n,INF,c[i][j]); 71 } 72 73 int spfa1() 74 { 75 rep(i,1,s) 76 { 77 dis[i]=INF; 78 inq[i]=0; 79 } 80 int t=0,w=1; 81 q[1]=S; dis[S]=0; inq[S]=1; 82 while(t<w) 83 { 84 t++; int u=q[t%(s+5)]; inq[u]=0; 85 int e=head[u]; 86 while(e) 87 { 88 int v=vet[e]; 89 if(len1[e]&&dis[u]+len2[e]<dis[v]) 90 { 91 dis[v]=dis[u]+len2[e]; 92 pre[v][0]=u; 93 pre[v][1]=e; 94 if(!inq[v]) 95 { 96 w++; q[w%(s+5)]=v; inq[v]=1; 97 } 98 } 99 e=nxt[e]; 100 } 101 } 102 if(dis[T]==INF) return 0; 103 return 1; 104 } 105 106 int spfa2() 107 { 108 rep(i,1,s) 109 { 110 dis[i]=-INF; 111 inq[i]=0; 112 } 113 int t=0,w=1; 114 q[1]=S; dis[S]=0; inq[S]=1; 115 while(t<w) 116 { 117 t++; int u=q[t%(s+5)]; inq[u]=0; 118 int e=head[u]; 119 while(e) 120 { 121 int v=vet[e]; 122 if(len1[e]&&dis[u]+len2[e]>dis[v]) 123 { 124 dis[v]=dis[u]+len2[e]; 125 pre[v][0]=u; 126 pre[v][1]=e; 127 if(!inq[v]) 128 { 129 w++; q[w%(s+5)]=v; inq[v]=1; 130 } 131 } 132 e=nxt[e]; 133 } 134 } 135 if(dis[T]==-INF) return 0; 136 return 1; 137 } 138 139 void mcf() 140 { 141 int k=T; 142 int t=INF; 143 while(k!=S) 144 { 145 int e=pre[k][1]; 146 t=min(t,len1[e]); 147 k=pre[k][0]; 148 } 149 ans1+=t; 150 k=T; 151 while(k!=S) 152 { 153 int e=pre[k][1]; 154 len1[e]-=t; 155 len1[e^1]+=t; 156 ans2+=t*len2[e]; 157 k=pre[k][0]; 158 } 159 } 160 161 void solve1() 162 { 163 addedge(); 164 ans1=ans2=0; 165 while(spfa1()) mcf(); 166 printf("%d\n",ans2); 167 } 168 169 void solve2() 170 { 171 addedge(); 172 ans1=ans2=0; 173 while(spfa2()) mcf(); 174 printf("%d\n",ans2); 175 } 176 177 int main() 178 { 179 //freopen("1.in","r",stdin); 180 n=read(),m=read(); 181 s=n+m,S=++s,T=++s; 182 rep(i,1,n) a[i]=read(); 183 rep(i,1,m) b[i]=read(); 184 rep(i,1,n) 185 rep(j,1,m) c[i][j]=read(); 186 solve1(); 187 solve2(); 188 }