看题:


思路:并查集
详细代码:
#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;
}