【题意】：
有N个人，M个仓库，每个人需要物品，个数都等于共同的K，仓库中有对应的K件物品的数量，随后给K个N*M矩阵（小写k, n, m表示K,N,M对应的子集），表明m个仓库到第n个人的位置运送k物品的花费，求
满足所有人的订单要求所需要的花费，如果不能满足所有人则输出-1
【思路】：
我的思路是建立源点sp，汇点tp, 把仓库和人所在的点都进行拆分，对每个仓库拆分成K个点，可以想象成一个大仓库由K个小仓库组成，每个小仓库只发放第k种物品，每个人也分成K个点，每个点接受一种k物品，sp与仓库的拆点进行连边，权重为这个小仓库存放的k物品的数量，花费为0，人的拆点与tp连边，权重为人拆点所需要的k物品的数量，费用为0，最后将仓库的拆点与人的拆点进行连边，权重为inf，费用为矩阵中对应的费用。
【重要】——>解决TLE问题
我的想法可能与网上的题解不同，我看有很多是分别跑k次费用流，最后的费用总和为结果，我在一开始也是疯狂TLE，然后加上特判就过了？
【特判】——>解决TLE
将输入分成三部分与N有关——与M有关——K个N*M矩阵
判定是否有供不应求的情况，将前两部分输入(N*K和N*K)分别存储下来，N*K代表所需要的部分，M*K代表供应的部分，对每个k进行遍历，然后求每个n的和sum1，每个m的和sum2，如果sum1>sum2则不对第三部分输入处理(K个N*M矩阵)，待输入结束后不进行费用流算法，直接输出-1即可
#include <iostream> #include <cstring> #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int maxn = 1e4 + 5; const int maxe = 1e6 + 5; const int N = 100 + 5; const int inf = 0x3f3f3f3f; struct edge{ int to, w, c, next; } ed[maxe]; int head[maxn], tot, ns; int n, m, k, ware[N][N], p[N][N]; int sp, tp, d[maxn], pre[maxn], a[maxn]; bool inq[maxn]; inline void init(){ memset( head, -1, sizeof(head) ) ; tot = 1; ns = (n+m)*k+2; sp = 0; tp = ns-1; } inline void add( int u, int v, int w, int c ){ ed[++tot].to = v; ed[tot].w = w; ed[tot].c = c; ed[tot].next = head[u]; head[u] = tot; ed[++tot].to = u; ed[tot].w = 0; ed[tot].c = -c; ed[tot].next = head[v]; head[v] = tot; } inline bool spfa( int &flow, int &cost ){ for( int i=0; i<ns; i++ ){ inq[i] = 0; d[i] = inf; } queue<int> q; d[sp] = pre[sp] = 0; a[sp] = inf; inq[sp] = 1; q.push(sp); while( q.size() ){ int x = q.front(); q.pop(); inq[x] = 0; for( int i=head[x]; ~i; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w>0 && d[y]>d[x]+ed[i].c ){ d[y] = d[x]+ed[i].c; pre[y] = i; a[y] = min(a[x], ed[i].w); if( !inq[y] ){ inq[y] = 1; q.push(y); } } } } if( d[tp]==inf ) return 0; flow += a[tp]; cost += a[tp]*d[tp]; for( int x=tp; x!=sp; x=ed[pre[x]^1].to ){ ed[pre[x]].w -= a[tp]; ed[pre[x]^1].w += a[tp]; } return 1; } inline void mcmf( int &flow, int &cost ){ while(spfa(flow, cost)); } int main(){ while( ~scanf("%d%d%d", &n, &m, &k), (n||m||k) ){ init(); int num, sum = 0; for( int i=1; i<=n; i++ ) for( int j=1; j<=k; j++ ){ scanf("%d", &p[i][j]); sum += p[i][j]; add( (i-1)*k+j, tp, p[i][j], 0 ); } for( int i=1; i<=m; i++ ) for( int j=1; j<=k; j++ ){ scanf("%d", &ware[i][j]); add( sp, (i-1)*k+j+n*k, ware[i][j], 0 ); } bool flag = 0; for( int i=1; i<=k; i++ ){ int sum1 = 0, sum2 = 0; for( int j=1; j<=n; j++ ) sum1 += p[j][i]; for( int j=1; j<=m; j++ ) sum2 += ware[j][i]; if( sum2<sum1 ) {flag = 1; break;} //判断是否存在供不应求，如果存在则直接输出-1 } for( int l=1; l<=k; l++ ) for( int i=1; i<=n; i++ ) for( int j=1; j<=m; j++ ){ int num; scanf("%d", &num); if( flag ) continue; //如果出现供不应求则不进行处理，只读取数据即可 add( (j-1)*k+l+n*k, (i-1)*k+l, inf, num ); } if( flag ){ puts("-1"); continue; } //输出-1 int flow = 0, cost = 0; mcmf(flow, cost); if( flow>=sum ) printf("%d ", cost); else puts("-1"); } return 0; }