【题意】：有n个商店，m个供应商，k种商品，给出每个商店对每种商品的需求，每个供应商对于每种商品的库存，和对于每种商品，每个供应商运到每个商店的费用。
问：能否满足每个商店的需求，如果能，输出最少的费用；否则输出-1。
【题解】：这是一场个人赛的题目，当时一开始没反应过来是最小费用流，到我意识到的时候已经没有时间敲代码了。
其实这题就是好裸的最小费用流，只需要注意一点，对于每一种商品各自构一次图，跑最小费用流即可。至今不明白为什么k个图没联系，弄在一起跑费用流会超时。
对于每个构图就是 s->供应商->商店->t，最后判断一下最大流是否等于各个商店的需求和即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "queue"
5 using namespace std;
6 #define maxm 1000005
7 #define maxn 50005
8 #define MAX 55
9 const int INF = 99999999;
10 int eh[maxn], tot, low[maxn], p[maxn], dist[maxn];
11 int s, t, ans, anscost, fans, fanscost;
12 bool visit[maxn];
13 int cap[MAX][MAX], need[MAX][MAX], cost[MAX][MAX][MAX];
14 struct Edge {
15 int u, v, cost, cap, flow, next;
16 }et[maxm];
17
18 void add(int u, int v, int cost, int cap, int flow) {
19 Edge E = {u, v, cost, cap, flow, eh[u]};
20 et[tot] = E;
21 eh[u] = tot++;
22 }
23
24 void addedge(int u, int v, int cost, int cap) {
25 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
26 }
27
28 void init() {
29 tot = 0;
30 memset(eh, -1, sizeof(eh));
31 }
32
33 int min(int a, int b) {
34 return a < b ? a : b;
35 }
36
37 bool spfa() {
38 queue<int> que;
39 memset(visit, false, sizeof(visit));
40 memset(p, -1, sizeof(p));
41 fill(&dist[0], &dist[maxn], INF);
42 visit[s] = true, low[s] = INF, dist[s] = 0;
43 que.push(s);
44 while(!que.empty()) {
45 int u = que.front();
46 que.pop();
47 visit[u] = false;
48 for(int i = eh[u]; i != -1; i = et[i].next) {
49 int v = et[i].v, cost = et[i].cost, flow = et[i].flow, cap = et[i].cap;
50 if(cap - flow && dist[u] + cost < dist[v]) {
51 dist[v] = dist[u] + cost;
52 p[v] = i;
53 low[v] = min(low[u], cap - flow);
54 if(!visit[v]) {
55 visit[v] = true;
56 que.push(v);
57 }
58 }
59 }
60 }
61 return dist[t] != INF;
62 }
63
64 void costflow() {
65 ans = 0, anscost = 0;
66 while(spfa()) {
67 int x = p[t];
68 ans += low[t];
69 anscost += low[t] * dist[t];
70 while(x != -1) {
71 et[x].flow += low[t];
72 et[x^1].flow -= low[t];
73 et[x^1].cost = -et[x].cost;
74 x = p[et[x].u];
75 }
76 }
77 }
78
79 int main() {
80 int n, m, k;
81 int i, j, l;
82 while(1) {
83 int sum = 0;
84 fans = fanscost = 0;
85 scanf("%d%d%d", &n, &m, &k);
86 if(!n && !m && !k) break;
87 for(i = 1; i <= n; i++) {
88 for(j = 1; j <= k; j++) {
89 scanf("%d", &need[i][j]);
90 sum += need[i][j];
91 }
92 }
93 for(i = 1; i <= m; i++) {
94 for(j = 1; j <= k; j++) {
95 scanf("%d", &cap[i][j]);
96 }
97 }
98 for(i = 1; i <= k; i++) {
99 for(j = 1; j <= n; j++) {
100 for(l = 1; l <= m; l++) {
101 scanf("%d", &cost[i][j][l]);
102 }
103 }
104 }
105 for(i = 1; i <= k; i++) {
106 init();
107 s = 0; t = n + m + 1;
108 for(j = 1; j <= m; j++) {
109 addedge(s, j, 0, cap[j][i]);
110 for(l = 1; l <= n; l++)
111 addedge(j, m + l, cost[i][l][j], INF);
112 }
113 for(j = 1; j <= n; j++)
114 addedge(m + j, t, 0, need[j][i]);
115 costflow();
116 fans += ans, fanscost += anscost;
117 }
118 if(sum != fans) fanscost = -1;
119 printf("%d\n", fanscost);
120 }
121 return 0;
122 }