某地区有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
题解:
贪心好题,想了好久。。。
枚举新工厂,先假设所有的煤全部转移到新工厂了,然后对于每个煤矿厂,记录把煤运到新工厂,和把煤运到旧工厂的成本差,从小到大排序,再一直往旧厂里加加加,一直加到满 B 为止。
计算总成本,更新答案即可。
代码如下:
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=50005;
4 const int inf=1e9;
5 int n,m,b,H;
6 struct node{
7 int pos,num,cha;
8 }c3[N];
9 int c1[N],c2[55][N],a[N],h[55],ans1,ans=inf;
10 inline bool cmp(node a,node b)
11 {
12 return a.cha<b.cha;
13 }
14 inline void doing(int pos)
15 {
16 int cost=h[pos]+H;
17 for (int i=1; i<=m; i++)
18 {
19 cost+=a[i]*c2[pos][i];
20 c3[i].cha=c1[i]-c2[pos][i];
21 c3[i].pos=i;
22 }
23 sort(c3+1,c3+1+m,cmp);
24 int tmp=b;
25 for (int i=1; i<=m; i++)
26 if (tmp)
27 {
28 if (tmp>=a[c3[i].pos])
29 {
30 cost+=a[c3[i].pos]*c3[i].cha;
31 tmp-=a[c3[i].pos];
32 }
33 else cost+=tmp*c3[i].cha,tmp=0;
34 }
35 else break;
36 if (cost < ans)
37 {
38 ans1=pos; ans=cost;
39 }
40 }
41 int main()
42 {
43 scanf("%d%d%d%d",&m,&b,&H,&n);
44 for (int i=1; i<=m; i++)
45 scanf("%d",&a[i]);
46 for (int i=1; i<=n; i++)
47 scanf("%d",&h[i]);
48 for (int i=1; i<=m; i++)
49 scanf("%d",&c1[i]);
50 for (int i=1; i<=n; i++)
51 for (int j=1; j<=m; j++)
52 scanf("%d",&c2[i][j]);
53 for (int i=1; i<=n; i++)
54 doing(i);
55 printf("%d\n%d\n",ans1,ans);
56 return 0;
57 }
View Code
加油加油加油!!!fighting fighting fighting!!!