看了下SPFA题解，一个一个太麻烦了，另一个写的很不清楚，而且注释都变成了"???"不知道怎么过的，于是自己来一发SPFA算法。

Part 1.题意

MM个仓库，卖给NN个商店，两个问，第一问求运价最小值，第二问最大值。

显然是一个最小费用最大流(MCMF)。

Part 2.思路

1.连让每个仓库连接一个超级源点SS，费用(dis)为0，流量为仓库的流量，表示每个仓库最多可以运出多少货物。

2.让每一个仓库连接每一家商店，边权为cost[i][j]cost[i][j]，其中，i为仓库编号，j为商店编号编号，流量为need[j]need[j]，其实流量可以取得范围是[need[j]...INF][need[j]...INF] ，另外如果出现need[j]need[j]<这个仓库货物量的情况也可以不怕(这时候取值的下限变成min(hw[i],need[j])min(hw[i],need[j])) hw指的是这家仓库的货物，还有注意编号的范围（我默认超级源点是00，仓库是1……n1……n,商店是n+1……n+mn+1……n+m，超级汇点是1000010000）

3.让每一家商店连接超级汇点TT

图像帮助理解：

Part 3.代码

现在代码就好办了
注释给的很清楚

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

#define I_copy_this_answer return 0;

using namespace std;

int n,m,head[1100],size=1;
int mmx=1000,mincost,maxwater;
int flow[1100];
int need[1100],cost[310][310];
int pre[1100],las[1100],dis[1100],vis[1100],hw[1100];

struct edge{
	int next,to,dis,flow; 
}e[100860]; 

void addedge(int next,int to,int dis,int flow)
{
	e[++size].to=to;
	e[size].dis=dis;
	e[size].flow=flow;
	e[size].next=head[next];
	head[next]=size;
}


int spfa(int s)
{
	memset(flow,0x3f,sizeof(flow));
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	queue <int> q;
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	pre[mmx]=-1;  //（其实只要不是与p直接连的点(n+1......n+m)就可以了 
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		int i,j,k,l;
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			k=e[i].dis;
			l=e[i].flow;
			if(dis[t]+k<dis[j]&&l>0)  //没有流量的话这条路就增广不了，最短距离是建立在增广路存在的基础上的 
			{
				dis[j]=dis[t]+k;
				las[j]=i;  //las指的是这个点(j)与上个点(t)相连的边的编号 
				pre[j]=t;  //pre指的是这条路径上这个点(j)的上一个点 
				flow[j]=min(flow[t],l);  //把当前边流量与上个点的流量对比，解决出现仓库货物比需要的少的情况 
				if(!vis[j])
				{
					q.push(j);
					vis[j]=1;
				}
			}
		}
	}
	return pre[mmx]!=-1;  //如果不是这个值就说明这个点被刷新，增广成功 
}

void mcmf()
{
	while(spfa(0))
	{
		mincost+=dis[mmx]*flow[mmx];   //从源点出发到汇点的单位费用再乘以单位，由于每次只增广一条路，而且仓库和商店是直接连接的，可以这样写 
		int t=mmx;
		while(t!=0)
		{
			e[las[t]].flow-=flow[mmx];  //回溯，修改每条边的流量，因为该算法中途找到的增广路不是最后的增广路，所以这个要等到最后来改变 
			e[las[t]^1].flow+=flow[mmx];
			t=pre[t];
		}
	}
}

void build_edge(int t)
{
	int i,j;
	for(i=1;i<=m;i++)
	{
		addedge(0,i,0,hw[i]);
		addedge(i,0,0,0);
	} 
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
	{
		addedge(i,j+m,cost[i][j]*t,need[j]);
		addedge(j+m,i,-cost[i][j]*t,0);
	}
	for(i=1;i<=n;i++)
	{
		addedge(i+m,mmx,0,need[i]);
		addedge(mmx,i+m,0,0);
	}
}

int main()
{
	int i,j;
	scanf("%d %d",&m,&n);
	for(i=1;i<=m;i++)
	{
		int t1;
		scanf("%d",&hw[i]);	
	}
	for(i=1;i<=n;i++)
		scanf("%d",&need[i]);
	for(i=1;i<=m;i++)
	for(j=1;j<=n;j++)
		scanf("%d",&cost[i][j]);  //读入，与上面的cost,need,hw如果不明白可以对照输入格式看代表什么意思 
	build_edge(1);  //建立边权为正的边，跑最小费用最大流 
	mcmf();//最小费用最大流(Min Cost Max Flow ）的缩写 
	printf("%d",mincost); 
	maxwater=0;
	mincost=0; 
	size=1;
	memset(head,0,sizeof(head));
	build_edge(-1);
	mcmf();
	printf("\n%d",-mincost);
	I_copy_this_answer
}