P1194 买礼物

Posted Sat Dec 07 2019. 1249 words. 6 min read.

This article was last updated on days ago, the information described in the article may be outdated.

题目

[1]

题目描述

又到了一年一度的明明生日了,明明想要买 B 样东西,巧的是,这 B 样东西价格都是 A 元。

但是,商店老板说最近有促销活动,也就是:

如果你买了第 I 样东西,再买第 J 样,那么就可以只花 KI,JK_{I,J} 元,更巧的是,KI,JK_{I,J} 竟然等于 KJ,IK_{J,I}

现在明明想知道,他最少要花多少钱。

输入格式

第一行两个整数,A,B。

接下来B行,每行 B 个数,第 I 行第 J 个为 KI,JK_{I,J}

我们保证 KI,J=KJ,IK_{I,J}=K_{J,I},并且 KI,I=0K_{I,I}=0

特别的,如果 KI,J=0K_{I,J}=0,那么表示这两样东西之间不会导致优惠。

输出格式

一个整数,为最小要花的钱数。

输入输出样例

输入 #1

1 1
0

输出 #1

1

输入 #2

3 3
0 2 4
2 0 2
4 2 0

输出 #2

7

说明/提示

样例解释 22

先买第 22 样东西,花费 33 元,接下来因为优惠,买 1,31,3 样都只要 22 元,共 77 元。

(同时满足多个“优惠”的时候,聪明的明明当然不会选择用 44 元买剩下那件,而选择用 22 元。)

数据规模

对于30%30\%的数据,1B101 \le B \le 10

对于100%100\%的数据,1B500,0A,KI,J10001 \le B \le 500,0 \le A,K_{I,J} \le 1000

2018.7.25 新添数据一组

代码

典型阅读理解题

B 个商品,都是 A …

一道最小生成树题,非常佩服出题者的思想%%%

谁能把买东西和最小生成树结合起来呢(最短路写 a+b 的大佬除外)

好题啊,在机房写的时候,几位巨佬都说是好题

认真读题发现 x-y 的边权其实就是买了之后再买 y 的价格

或者买了 y 之后再买 x 的价格

那这样就很好做了

不过这题的输入和普通的题不一样,普通题给的是一组一组的边,而这题给了个邻接矩阵 ,为了方便我在输入的时候转成了用结构体来存

struct Edge {
int u,v,w;
}edge[MAXM];
// B 为邻接矩阵的边长
for(int i=1;i<=B;i++)
for(int j=1;j<=B;j++) {
cin >> t;
if(i==j) continue;
++cnt;
if(t==0) edge[cnt].w = A;
else edge[cnt].w = t;
edge[cnt].u = i;
edge[cnt].v = j;
}

存图完成,接下来跑一遍 kruskal 就 ok 了

int find(int x) {
if(f[x]==x)
return x;
return f[x] = find(f[x]);
}
bool cmp(Edge a,Edge b) {
return a.w < b.w;
}

for(int i=1;i<=B;i++)
f[i] = i;
sort(edge+1,edge+cnt+1,cmp);
for(int i=1;i<=cnt;i++) {
if(sum+1==B)
break;
int x = find(edge[i].u);
int y = find(edge[i].v);
if(x!=y) {
f[x] = y;
sum++;
ans += edge[i].w;
}

这么简单?当然不可能,这时候再认真思考下 ans 存的是什么?

边的权值相加,那权值表示商品的价格,可总共 B 个商品,但我们直连了 B-1 条边,所以最后还要加上一个商品的原价 A。

那么让 ans 的初值为 A 即可

综上,把代码合起来,整理下就 ok 了。

然后我就 90 分了 QAQ

最后一个点 wa 了?

下个测试点

输入数据

3 3
0 4 4
4 0 4
4 4 0

输出数据

9

问题马上就出来了,商品原价 3 元,可买了某一个再买另一个居然还要 4 块?促销不应该更便宜吗

那既然这样,当权值大于 A 的时候就把 A 作权值,修改下存图的代码就好了

for(int i=1;i<=B;i++)
for(int j=1;j<=B;j++) {
cin >> t;
if(i==j) continue;
cnt++;
if(t==0 || t>A) edge[cnt].w = A;
else edge[cnt].w = t;
edge[cnt].u = i;
edge[cnt].v = j;
}

最后附上 AC 代码

#include <algorithm>
#include <iostream>
#include <cstdio>
#define MAXN 50000
#define MAXM 25000000
using namespace std;

int t,A,B,cnt,ans,sum;
int f[MAXN];
struct Edge {
int u,v,w;
}edge[MAXM];

int find(int x) {
if(f[x]==x)
return x;
return f[x] = find(f[x]);
}
bool cmp(Edge a,Edge b) {
return a.w < b.w;
}

int main() {
cin >> A >> B;
for(int i=1;i<=B;i++)
for(int j=1;j<=B;j++) {
cin >> t;
if(i==j) continue;
cnt++;
if(t==0 || t>A)// 注意 t>A 则存入 A
edge[cnt].w = A;
else
edge[cnt].w = t;
edge[cnt].u = i;
edge[cnt].v = j;
}
ans += A;// 注意 ans 的初值
for(int i=1;i<=B;i++)
f[i] = i;
sort(edge+1,edge+cnt+1,cmp);
for(int i=1;i<=cnt;i++) {
if(sum+1==B)
break;
int x = find(edge[i].u);
int y = find(edge[i].v);
if(x!=y) {
sum++;
f[x] = y;
ans += edge[i].w;
}
}
cout << ans;
return 0;
}


Comments

Unable to load Disqus, please make sure your network can access.