题目链接
nyist最终淘汰赛第一场 - Virtual Judge (csgrandeur.cn)
一些话
绝大多数的最小生成树题目都是因为没有好好看题导致卡题
这次卡题原因是看错题意导致输入部分的代码出问题，没有正确储存数据
要一字一句读题
想用结构体写并查集，发现不会，去查了下
流程
此题需要用并查集确认连通情况，因此用kruscal更合适
找到最小生成树的n（点数）m（边数）和边的数据（a,b,w)再套模板即可
套路
结构体并查集
struct Parent{ int f; }p[N]; f[x] 用 p[x].f 来代替;
ac代码
//需要解决的难点是如何把f[]写进结构体来一起排序x //结论，f[]不能写进结构体排序，排序后会打乱并查集结构x //看错题意得到了上面的傻逼结论， #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e3 + 10; int f[N]; struct Dist{ int a,b,w; bool operator<(const Dist& W)const{ return w < W.w; } }dist[N]; int n,m; int find(int x){ if(x != f[x]) f[x] = find(f[x]); return f[x]; } int kruskal(){ int res = 0; sort(dist,dist+n*n); for(int i = 0;i < n*n;i++){ int a = dist[i].a,b = dist[i].b,w = dist[i].w; // cout << a << " " <<b << " " << w << endl; a = find(a),b = find(b); // cout << i << " " << a << " " << b << endl; if(a != b){ res+=w; f[a] = b; } } return res; } int main(){ cin >> n; for(int i = 0;i < n;i++){ f[i] = i; } int cnt = 0; for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ int x; cin >> x; dist[cnt++] = {i,j,x}; } } cin >> m; for(int i = 0;i < m;i++){ int a,b; cin >> a >> b; a = find(a),b = find(b); // cout << i << " " << a << " " << b << endl; if(a != b) f[a] = b; } int t = kruskal(); cout << t << endl; return 0; }
