题目描述
又到了一年一度的明明生日了，明明想要买B样东西，巧的是，这B样东西价格都是A元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第II样东西，再买第J样，那么就可以只花KI,J元，更巧的是，KI,J竟然等于KJ,I。
现在明明想知道，他最少要花多少钱。
输入输出格式
输入格式：
第一行两个整数，A,B。
接下来BB行，每行B个数，第I行第J个为KI,J。
我们保证KI,J=KJ,I并且KI,I=0。
特别的，如果KI,J=0，那么表示这两样东西之间不会导致优惠。
输出格式：
一个整数，为最小要花的钱数。
输入输出样例
说明
样例解释2
先买第2样东西，花费3元，接下来因为优惠，买1,3样都只要2元，共7元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用4元买剩下那件，而选择用2元。）
数据规模
对30%的数据,1≤B≤10。
对于100%的数据,1≤B≤500,0≤A,KI,J≤1000。
思路：直接求一边最小生成树，然后加上买第一件物品所花的费用，即A
注意：在原价比优惠价便宜时，应取优惠价
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<ctime>
using namespace std;
const int M = ;
int n, m, k, tot, sum;
int fa[M];
struct nond {
int u, v, w;
}e[M]; int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
} bool cmp(nond x, nond y) {
return x.w < y.w;
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) fa[i] = i;
for(int i = ; i <= m; i++)
for(int j = ; j <= m; j++) {
int a;
scanf("%d", &a);
if(a != && i < j) {
e[++k].u = i;
e[k].v = j;
e[k].w = a;
}
}
sort(e+, e+k+, cmp);
for(int i = ; i <= k; i++) {
int x = find(e[i].u), y = find(e[i].v);
if(x == y) continue;
srand(time() + );
if(rand()%) fa[x] = y;
else fa[y] = x;
tot++;
sum += e[i].w;
if(tot == n-) break;
}
sum += n;
printf("%d\n", sum);
return ;
}
90分，没有考虑原价低于优惠价的情况
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int M = ;
int n, m, tot, sum, k;
int fa[M], f[M];
struct nond {
int u, v, w;
}e[M]; int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
} bool cmp(nond x, nond y) {
return x.w < y.w;
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) fa[i] = i;
for(int i = ; i <= m; i++)
for(int j = ; j <= m; j++) {
int a;
scanf("%d", &a);
if(a != && i < j) {
e[++k].u = i;
e[k].v = j;
e[k].w = a;
}
}
sort(e+, e+k+, cmp);
for(int i = ; i <= k; i++) {
int x = find(e[i].u), y = find(e[i].v);
if(x == y) continue;
fa[x] = y;
tot++;
sum += min(n, e[i].w);
if(tot == n-) break;
}
sum += n;
printf("%d\n", sum);
return ;
}
AC代码