1 条题解

  • 0
    @ 2024-12-24 10:06:07

    C++ :

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    struct vi {
    	int start;
    	int end;
    	int cost;
    } edge[5000], et;
    
    int p[101];
    
    int Find(int n) {
    	return n == p[n] ? n : p[n] = Find(p[n]);
    }
    
    bool cmp(vi a, vi b) {
    	return a.cost < b.cost;
    }
    
    int main() {
    	int n, m, i, k, sum, flag, ST, EN;
    	while (scanf("%d%d", &n, &m) != EOF, n) {
    		for (i = 1; i <= m; i++)
    			p[i] = i;
    		for (k = i = 0; i < n; i++) {
    			scanf("%d%d%d", &et.start, &et.end, &et.cost);
    			edge[k++] = et;
    		}
    		sort(edge, edge + k, cmp);
    		for (sum = i = 0; i < k; i++) {
    			ST = Find(edge[i].start);
    			EN = Find(edge[i].end);
    			if (ST != EN) {
    				p[ST] = EN;
    				sum += edge[i].cost;
    			}
    		}
    		for (flag = 0, i = 1; i <= m; i++)
    			if (p[i] == i)
    				flag++;
    		if (flag == 1)
    			printf("%d\n", sum);
    		else
    			puts("Error!");
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    1951
    时间
    1000ms
    内存
    32MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者