看题:
思路:并查集
详细代码:
#include<iostream>//并查集思想,此题有考虑到MST不存在的情况,要自己构造,先把flag=1的节点加入到集合 #include<cmath> #include<algorithm> #include<iomanip> using namespace std; #define N 101 int tree[N];//保存各个节点的根节点 struct e//结构体保存两个节点之间的cost(距离,时间,建路建桥花费之类的) { int a, b; int cost; bool flag;//此题有标志,1表示已修了路,0表示没修 bool operator<(const e& s)const//重载<号 { if (flag != s.flag)//flag=1的排在最前面,以便等下遍历的时候,把已经修了路的节点先放入一个集合中 return flag > s.flag; else { if (cost != s.cost)//flag=0时,按照修路花费最少的排在前面 return cost < s.cost; else//这个随便 你a小排前还是b小排前不影响 return a < s.a; } } }edg[5500]; int findroot(int x)//找各个节点所在树的根节点 { if (tree[x] == -1)return x;//找到根节点,输出根节点 else//路径压缩,比如1-2-3,3的祖先节点是2,进行路径压缩,递归查找2的祖先节点=1, { //将3的祖先节点设为1,即1-2,1-3,此时1-3这条边的权值=以前2-3的权值,其实只是移动了边; int tmp = findroot(tree[x]); tree[x] = tmp; return tmp; } } int main() { int n; while (cin >> n && n != 0) { for (int i = 1; i <= n; i++)//一开始的节点都是单独的连通分量 tree[i] = -1; for (int i = 1; i <= n * (n - 1) / 2; i++)//输入数据 cin >> edg[i].a >> edg[i].b >> edg[i].cost >> edg[i].flag; sort(edg + 1, edg + 1 + n * (n - 1) / 2);//排序 int ans = 0; for (int i = 1; i <= n * (n - 1) / 2; i++) { int a = findroot(edg[i].a);//查找两个点的根节点 int b = findroot(edg[i].b); if (a != b)//a!=b,说明两点不是在同一棵树上,要将其合并成同一个集合 { tree[a] = b;// 将其合并成同一个集合,一棵树变成另一棵树根节点的子树 if (edg[i].flag != 1)//判断,如果flag=1,则路已修不用再花费,反之,flag=0,要修路ans+=edg[i].cost,因为当flag=0时,我们的 //edg数组是按cost的升序排列的,所以先修花费小的路,如果题中表示没有已修的,就和我上篇题一样,解法一致 { ans += edg[i].cost; } } }//当所有的节点都在一棵树的时候,ans保持不变,直至循环退出,ans即为最小花费 cout << ans << endl; } return 0; }