- /*
- * @Author: Lyucheng
- * @Date: 2017-07-22 11:40:20
- * @Last Modified by: Lyucheng
- * @Last Modified time: 2017-07-22 15:44:49
- */
- /*
- 题意:给你一个图然后求最小生成树
- 思路:裸的
- */
- #include < stdio.h > #include < string.h > #include < iostream > #include < algorithm > #include < vector > #include < queue > #include < set > #include < map > #include < string > #include < math.h > #include < stdlib.h > #include < time.h >
- #define MAXN 105
- using namespace std;
- struct Node {
- int u,
- v;
- int val;
- Node() {}
- Node(int x, int y, int z) {
- u = x;
- v = y;
- val = z;
- }
- bool operator < (const Node & other) const {
- return val < other.val;
- }
- };
- int n;
- int x;
- vector < Node > edge;
- int bin[MAXN];
- int findx(int x) {
- int cur = x;
- while (x != bin[x]) {
- x = bin[x];
- }
- bin[cur] = x;
- return x;
- }
- void init() {
- edge.clear();
- for (int i = 0; i <= n; i++) {
- bin[i] = i;
- }
- }
- int main() {
- // freopen("in.txt", "r", stdin);
- // freopen("out.txt", "w", stdout);
- while (scanf("%d", &n) != EOF) {
- init();
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- scanf("%d", &x);
- if (i == j) continue;
- edge.push_back(Node(i, j, x));
- }
- }
- int res = 0;
- sort(edge.begin(), edge.end());
- for (int i = 0; i < edge.size(); i++) {
- int fx = findx(edge[i].u);
- int fy = findx(edge[i].v);
- if (fx != fy) {
- res += edge[i].val;
- bin[fx] = fy;
- }
- }
- printf("%d\n", res);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2221768.html