题意：有n个店主，m个供应商，k种物品。告诉你每个店主需要多少第k个物品，每个供应商能提供多少第k个物品。不同店主从不同供应商那进货的价格也是不一样的。求满足所有店主进货需求的最小费用。
思路：首先，对于每种物品供大于求才能满足所有店主的需求。然后对每种物品分别建图，累加最大流最小费用。分别建图一次只要102个点，一开始建了5002个点，TLE
#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<stdlib.h> #include<math.h> #include<vector> #include<list> #include<map> #include<stack> #include<queue> #include<algorithm> #include<numeric> #include<functional> using namespace std; typedef long long ll; const int maxn = 105; int n,m,k; struct edge { int to,cf,w,rev; }; int d[maxn],fa[maxn],inq[maxn],pr[maxn]; vector<struct edge> v[maxn]; int nn[maxn][maxn],mm[maxn][maxn],xu[maxn],gong[maxn]; char mei[100005]; void init(int x) { for(int i = 0; i <= x; i++) v[i].clear(); } void add(int from,int to,int cap,int cost) { v[from].push_back((edge){to,cap,cost,v[to].size()}); v[to].push_back((edge){from,0,-cost,v[from].size()-1}); } int mincost(int s,int t) { queue<int> q; while(!q.empty()) q.pop(); int c,f; c = f = 0; while(1) { memset(fa,-1,sizeof fa); memset(d,0x3f,sizeof d); d[s] = 0; memset(inq,0,sizeof inq); q.push(s); while(!q.empty()) { int x = q.front();q.pop(); inq[x] = 0; for(int i = 0; i < v[x].size(); i++) { edge e = v[x][i]; int y = e.to; if(e.cf && d[y] > d[x] + e.w) { d[y] = d[x] + e.w; fa[y] = x; pr[y] = i; if(!inq[y]) { inq[y] = 1; q.push(y); } } } } if(d[t] == 0x3f3f3f3f) break; int gen = 0x3f3f3f3f; for(int a = t; a != s; a = fa[a]) gen = min(gen,v[fa[a]][pr[a]].cf); for(int a = t; a != s; a = fa[a]) { edge &e = v[fa[a]][pr[a]]; e.cf -= gen; v[a][e.rev].cf += gen; } f += gen; c += gen * d[t]; } return c;//f 最大流，c最小费用 } int main(void) { int i,j,tp; while(scanf("%d%d%d",&n,&m,&k)!=EOF && n+m+k) { int s = 1; int t = 2+n+m; memset(xu,0,sizeof xu); memset(gong,0,sizeof gong); for(j = 1; j <= n; j++) { for(i = 1; i <= k; i++) { scanf("%d",&nn[j][i]); xu[i] += nn[j][i]; } } for(j = 1; j <= m; j++) { for(i = 1; i <= k; i++) { scanf("%d",&mm[j][i]); gong[i] += mm[j][i]; } } int flag = 1; for(i = 1; i <= k; i++) { if(xu[i] > gong[i]) { flag = 0; break; } } int ans = 0; getchar(); for(int c = 1; c <= k; c++) { if(!flag) { for(i = 1; i <= n; i++) gets(mei); continue; } init(t); for(i = 1; i <= n; i++) add(1,i+1,nn[i][c],0); for(i = 1; i <= m; i++) add(i+1+n,t,mm[i][c],0); for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { scanf("%d",&tp); int a,b; { a = 1+i; b = 1+n+j; add(a,b,v[j+1+n][ v[t][j-1].rev ].cf,tp); } } } ans += mincost(s,t); } if(flag) printf("%d\n",ans); else printf("-1\n"); } return 0; }
