某地区有m座煤矿，其中第i号矿每年产量为ai吨，现有火力发电厂一个，每年需用煤b吨，每年运行的固定费用（包括折旧费，不包括煤的运费）为h元，每吨原煤从第i号矿运到原有发电厂的运费为Ci0（i=1，2，…，m）。
现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂，每年运行的固定费用为hj元。每吨原煤从第i号矿运到j号备选厂址的运费为Cij（i=1，2，…，m；j=1，2，…，n）。
试问：应把新厂厂址选取在何处？m座煤矿开采的原煤应如何分配给两个发电厂，才能使每年的总费用（发电厂运行费用与原煤运费之和）为最小。
第1行： m b h n
第2行： a1 a2 … am （0<=ai<=500, a1+a2+...+an>=b）
第3行： h1 h2 … hn （0<=hi<=100）
第4行： C10 C20 … Cm0 （0<=Cij<=50）
第5行： C11 C21 … Cm1
… …
第n+4行：C1n C2n … Cmn
第1行：新厂址编号，如果有多个编号满足要求，输出最小的。
第2行：总费用
对于所有数据, n<=50, m<=50000, b<=10000
枚举一下选择哪个新工厂，然后贪心的分配每个煤矿的分配即可得到当前的最有答案，更新全局最优解。
1 #include <bits/stdc++.h> 2 3 #define rep(i,x,y) for(int i=x;i<=y;++i) 4 5 template <class T> 6 inline void read(T &x) 7 { 8 static char c; 9 10 x = 0; 11 c = getchar(); 12 while (c < 48)c = getchar(); 13 while (c > 47)x = x * 10 + c - ‘0‘, c = getchar(); 14 } 15 16 const int mxn = 55; 17 const int mxm = 50005; 18 const int inf = 1E9 + 7; 19 20 int m, b, h, n; 21 22 int A[mxm]; 23 int H[mxn]; 24 int C[mxn][mxm]; 25 26 int ans = inf, id = 0; 27 28 int seq[mxm], sub[mxm]; 29 30 inline bool cmp(int a, int b) 31 { 32 return sub[a] < sub[b]; 33 } 34 35 inline void calculate(int t) 36 { 37 int cost = h + H[t], tmp = b; 38 39 rep (i, 1, m)cost += A[i] * C[t][i]; 40 rep (i, 1, m)seq[i] = i, sub[i] = C[0][i] - C[t][i]; 41 42 std::sort(seq + 1, seq + m + 1, cmp); 43 44 45 rep (i, 1, m)if (tmp) 46 { 47 int q = seq[i]; 48 49 if (tmp >= A[q]) 50 cost += sub[q] * A[q], tmp -= A[q]; 51 else 52 cost += sub[q] * tmp, tmp = 0; 53 } 54 55 if (ans > cost) 56 ans = cost, id = t; 57 } 58 59 signed main(void) 60 { 61 read(m); 62 read(b); 63 read(h); 64 read(n); 65 66 rep (i, 1, m)read(A[i]); 67 rep (i, 1, n)read(H[i]); 68 rep (i, 0, n)rep (j, 1, m)read(C[i][j]); 69 70 rep (i, 1, n)calculate(i); 71 72 printf("%d\n%d\n", id, ans); 73 } 74
@Author: YouSiki
原文：http://www.cnblogs.com/yousiki/p/6412488.html