弃用的分类（c++|P1194 买礼物-最小生成树）弃用的分类：c++|图论

题目描述又到了一年一度的明明生日了，明明想要买 BB 样东西，巧的是，这 BB 样东西价格都是 AA 元。
但是，商店老板说最近有促销活动，也就是：
【弃用的分类（c++|P1194 买礼物-最小生成树）】如果你买了第 II 样东西，再买第 JJ 样，那么就可以只花 KI,JK I , J 元，更巧的是， KI,JK I , J 竟然等于 KJ,IK J , I 。
现在明明想知道，他最少要花多少钱。
输入输出格式输入格式：

第一行两个整数， A,BA , B 。
接下来 BB 行，每行 BB 个数，第 II 行第 JJ 个为 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 % 的数据, 1≤B≤101 ≤ B ≤ 10 。
对于 100%100 % 的数据, 1≤B≤500,0≤A,KI,J≤10001 ≤ B ≤ 500 , 0 ≤ A , K I , J ≤ 1000 。

这是一道最小生成树的题目，解答这道题的关键就是把它转化成最小生成树模型，然后就基本上是裸的最小生成树啦。
但是还得注意两个问题。
一、“优惠购买”可能比原价还要贵，所以应该进行一下特判，如果选入的边比原价还要大的话，就按原价购买。
二、这个问题没有涉及，但应该考虑到的。那就是这张图可能不联通，所以应该判断有多少个联通块，再进行计算。
最后一个我自己的小问题，写代码时把n当成了m，以至于交了好几次莫名其妙全错。
AC Code

#include #include #include using namespace std; struct Edge { int from, to, cost; Edge(int f, int t, int c): from(f), to(t), cost(c) {} }; bool cmp(Edge x, Edge y) { return x.cost < y.cost; }const int maxn = 505; int n, m, father[maxn], ans = 0; vector edge; int find(int x) { return x == father[x] ? x : father[x] = find(father[x]); }int main() { for (int i = 1; i < maxn; ++i) { father[i] = i; } cin >> n >> m; for (int i = 1; i <= m; ++i) { for (int j = 1, c; j <= m; ++j) { cin >> c; if (c == 0) continue; edge.push_back(Edge(i, j, c)); } } sort(edge.begin(), edge.end(), cmp); for (size_t i = 0; i < edge.size(); ++i) { int x = find(edge[i].from), y = find(edge[i].to); int cost = edge[i].cost; if (x == y) continue; father[x] = y; ans += cost > n ? n : cost; } for (int i = 1; i <= m; ++i) { if (father[i] == i) ans += n; } cout << ans; }