看题：


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