最小生成树

目录

〇，切分定理

一，Kruskal

POJ 2349 Arctic Network

力扣 1584. 连接所有点的最小费用

力扣 1135. 最低成本联通所有城市

力扣 1168. 水资源分配优化

二，Prim

力扣 1584. 连接所有点的最小费用

三，所有最小生成树的交集、并集

力扣 1489. 找到最小生成树里的关键边和伪关键边

四，带黑白名单的最小生成树

---

〇，切分定理

在一幅连通加权无向图中，给定任意的切分，如果有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树中的一条边。

(B, C), (A, C), (A, D), (E, D) 均为「横切边」，其中BC一定属于最小生成树。

一，Kruskal

算法思路：

开始把每个点当做一棵独立的树，每次选所有不在一棵树上的两点构成的边中的最短边，把这两点连起来，两棵树合并成一棵树，

每次连一条边，直到所有的点都连成一棵树。

 

模板代码：

struct Edge
{
	int a;//端点id
	int b;//端点id
	int dist;
};
class Kruskal
{
public:
	//计算最小生成树，结果按照边从小到大排序,出参treeNum是森林中树的数量
	static vector<Edge> minCostConnectPoints(int n, vector<Edge> &v, int &treeNum)
	{
		sort(v.begin(), v.end(), cmp);
		Union unions(n);
		vector<Edge>ans;
		for (int i = 0, j = 0; j < n - 1 && i < v.size(); i++)
		{
			if (unions.inSame(v[i].a, v[i].b))continue;
			unions.merge(v[i].a, v[i].b);
			ans.push_back(v[i]);
			j++;
		}
		treeNum = unions.getRootNums();
		return ans;
	}
private:
	static bool cmp(Edge& a, Edge& b)
	{
		return a.dist < b.dist;
	}
};

时间复杂度：O（ElogE），其中E是边的数量。

POJ 2349 Arctic Network

题目：

Description

The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel. 
Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts. 

Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.

Input

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000).

Output

For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.

Sample Input
1
2 4
0 100
0 300
0 600
150 750

Sample Output

212.13

这个题目是说，有p个站点，其中有s个可以卫星相连。（卫星不是站点）

剩下还有p-s个站点，所以还需要用p-s条直线段把这p个站点全部连接起来。

求最长的直线段至少有多长。

比如本题，我们选0,300和0,600连接卫星，

0,100用200的线段可以连上0,300,150,750用150*sqrt(2)的线段可以连上0,600

所以答案是150*sqrt(2)=212.13

所以说，这个题目的意思就是，给你p个点的坐标，所有的点都是相连的，

选1个生成树，较大的s-1条边可以用卫星代替，较小的p-s条边中，最长的那个，至少有多长？

这个题目很明显就是克鲁斯卡尔(Kruskal)算法了。

代码：

#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<map>
using namespace std;

const int N = 500; //点的最大数量
int en; //点的数量
// 用数组或者vector记录点的信息，id要从0开始
struct node
{
	int x;
	int y;
};
node nod[N];

int fa[N];
int find(int x)	//找祖先
{
	if (fa[x] == x)return x;
	return fa[x] = find(fa[x]);
}
void merge(int i, int j)
{
	fa[find(i)] = j;
}
bool inSameSet(int i, int j)
{
	return find(i) == find(j);
}

struct Edge
{
	int a;//端点id
	int b;//端点id
	int dist;
};

bool cmp(Edge a, Edge b)
{
	return a.dist < b.dist;
}

int getLen(int i, int j) // 计算id为i和j的2个点的距离
{
	return (nod[j].x - nod[i].x) * (nod[j].x - nod[i].x)
		+ (nod[j].y - nod[i].y) * (nod[j].y - nod[i].y);
}
vector<Edge> getEdge() // 获取所有的边
{
	// TODO 根据实际情况修改
	vector<Edge> v;
	for (int i = 0; i < en; i++)for (int j = i + 1; j < en; j++) {
		Edge e = { i,j,getLen(i,j) };
		v.push_back(e);
	}
	return v;
}

int treeNum;//森林中树的数量
//计算最小生成树，结果按照边从小到大排序,并自动刷新treeNum
vector<Edge> minCostConnectPoints()
{
	vector<Edge> v = getEdge();
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < en; i++)fa[i] = i;
	vector<Edge>ans;
	for (int i = 0, j = 0; j < en - 1 && i < v.size(); i++)
	{
		if (inSameSet(v[i].a, v[i].b))continue;
		merge(v[i].a, v[i].b);
		ans.push_back(v[i]);
		j++;
	}
	map<int, int>m;
	for (int i = 0; i < en; i++)m[find(i)]++;
	treeNum = m.size();
	return ans;
}

int main()
{
	int t, s;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> s >> en;
		for (int j = 0; j < en; j++)
		{
			cin >> nod[j].x >> nod[j].y;
		}
		vector<Edge> v = minCostConnectPoints();
		Edge pa = v[en - s - 1];
		double c = 1.0;
		cout << fixed << setprecision(2) << sqrt(c * getLen(pa.a, pa.b)) << endl;
	}
	return 0;
}

力扣 1584. 连接所有点的最小费用

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
示例 2：

输入：points = [[3,12],[-2,5],[-4,1]]
输出：18
示例 3：

输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4
示例 4：

输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000
示例 5：

输入：points = [[0,0]]
输出：0
 

提示：

1 <= points.length <= 1000
-106 <= xi, yi <= 106
所有点 (xi, yi) 两两不同。

const int N = 1000; //点的最大数量
int en; //点的数量
// TODO 用数组或者vector记录点的信息，id要从0开始
vector<vector<int>>p;
 
int fa[N];
int find(int x)	//找祖先
{
    if (fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}
void merge(int i, int j)
{
    fa[find(i)] = j;
}
bool inSameSet(int i, int j)
{
    return find(i) == find(j);
}
 
struct Edge
{
    int a;//端点id
    int b;//端点id
    int dist;
};
 
bool cmp(Edge a, Edge b)
{
    return a.dist < b.dist;
}
 
int getLen(int i, int j) // 计算id为i和j的2个点的距离
{
    return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);
}
vector<Edge> getEdge() // 获取所有的边
{
    // TODO 根据实际情况修改
    vector<Edge> v;
    for (int i = 0; i < en; i++)for (int j = i + 1; j < en; j++) {
        Edge e = { i,j,getLen(i,j) };
        v.push_back(e);
    }
    return v;
}
 
int treeNum;//森林中树的数量
//计算最小生成树，结果按照边从小到大排序,并自动刷新treeNum
vector<Edge> minCostConnectPoints2()
{
	vector<Edge> v = getEdge();
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < en; i++)fa[i] = i;
	vector<Edge>ans;
	for (int i = 0, j = 0; j < en - 1 && i < v.size(); i++)
	{
		if (inSameSet(v[i].a, v[i].b))continue;
		merge(v[i].a, v[i].b);
		ans.push_back(v[i]);
		j++;
	}
	map<int, int>m;
	for (int i = 0; i < en; i++)m[find(i)]++;
	treeNum = m.size();
	return ans;
}
 
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        p = points;
        en = p.size();
        vector<Edge> v = minCostConnectPoints2();
        int ans = 0;
        for (auto &vi : v) {
            ans += getLen(vi.a, vi.b);
        }
        return ans;
    }
};

力扣 1135. 最低成本联通所有城市

想象一下你是个城市基建规划者，地图上有 n 座城市，它们按以 1 到 n 的次序编号。

给你整数 n 和一个数组 conections，其中 connections[i] = [xi, yi, costi] 表示将城市 xi 和城市 yi 连接所要的costi（连接是双向的）。

返回连接所有城市的最低成本，每对城市之间至少有一条路径。如果无法连接所有 n 个城市，返回 -1

该 最小成本 应该是所用全部连接成本的总和。

示例 1：

输入：n = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
输出：6
解释：选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。
示例 2：

输入：n = 4, conections = [[1,2,3],[3,4,4]]
输出：-1
解释：即使连通所有的边，也无法连接所有城市。
 

提示：

1 <= n <= 104
1 <= connections.length <= 104
connections[i].length == 3
1 <= xi, yi <= n
xi != yi
0 <= costi <= 105

vector<Edge> getEdge(vector<vector<int>>&p) // 获取所有的边
{
	vector<Edge> v;
	for (int i = 0; i < p.size(); i++) {
		Edge e = { p[i][0] - 1,p[i][1] - 1,p[i][2] };
		v.push_back(e);
	}
	return v;
}

class Solution {
public:
	int minimumCost(int n, vector<vector<int>>& connections) {
		auto es = getEdge(connections);
		int treeNum;
		vector<Edge> v = KruskalMinCostTree(n, es, treeNum);
		if (treeNum > 1)return -1;
		int s = 0;
		for (auto& vi : v)s += vi.dist;
		return s;
	}
};

力扣 1168. 水资源分配优化

村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。

对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井，成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）；另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[j] = [house1j, house2j, costj] 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。

请返回 为所有房子都供水的最低总成本 。

示例 1：

输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
输出：3
解释： 
上图展示了铺设管道连接房屋的成本。
最好的策略是在第一个房子里建造水井（成本为 1），然后将其他房子铺设管道连起来（成本为 2），所以总成本为 3。

示例 2：

输入：n = 2, wells = [1,1], pipes = [[1,2,1]]
输出：2
解释：我们可以用以下三种方法中的一种来提供低成本的水:
选项1:
在1号房子里面建一口井，成本为1
在房子2内建造井，成本为1
总成本是2。
选项2:
在1号房子里面建一口井，成本为1
-花费1连接房子2和房子1。
总成本是2。
选项3:
在房子2内建造井，成本为1
-花费1连接房子1和房子2。
总成本是2。
注意，我们可以用cost 1或cost 2连接房子1和房子2，但我们总是选择最便宜的选项。

提示：

• 2 <= n <= 104
• wells.length == n
• 0 <= wells[i] <= 105
• 1 <= pipes.length <= 104
• pipes[j].length == 3
• 1 <= house1j, house2j <= n
• 0 <= costj <= 105
• house1j != house2j

vector<Edge> getEdge(vector<vector<int>>& p) // 获取所有的边
{
	vector<Edge> v;
	for (int i = 0; i < p.size(); i++) {
		Edge e = { p[i][0],p[i][1],p[i][2] };
		v.push_back(e);
	}
	return v;
}

class Solution {
public:
	int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
		auto p = pipes;
		for (int i = 0; i < n; i++)p.push_back(vector<int>{0, i + 1, wells[i]});
		vector<Edge> v = getEdge(p);
		int treeNum, sumDist=0;
		v = KruskalMinCostTree(n + 1, v, treeNum);
		for (auto vi : v)sumDist += vi.dist;
		return sumDist;
	}
};

二，Prim

Prim和Dijkstra几乎一样，区别只在于Dijkstra的距离的每个点到起点的路径总长，而Prim的距离就是每个点到最近一个点的距离。

 

模板代码：

class Prim
{
	//计算最小生成树，结果按照边从小到大排序
	static vector<pair<int, int>> minCostConnectPoints(int n, map<pair<int, int>, int>& value)
	{
		vector<bool>visit_(n);
		vector<int>minLen(n);
		for (int i = 0; i < n; i++) {
			minLen[i] = INT_MAX;
			visit_[i] = false;
		}
		minLen[getStartId(n, value)] = INT_MIN;
		vector<pair<int, int>>ans;
		for (int i = 0; i < n; i++) {
			int id = getId(n, visit_, minLen);
			for (int j = 0; j < n; j++) {
				if (visit_[j] && value[make_pair(id, j)] == minLen[id]) {
					ans.push_back(make_pair(id, j));
					break;
				}
			}
			visit_[id] = true;
			fresh(n, visit_, minLen, value, id);
		}
		return ans;
	}
private:
	static int getStartId(int n, map<pair<int, int>, int>& value)
	{
		int m = INT_MAX;
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i != j && m > value[make_pair(i, j)]) {
					m = value[make_pair(i, j)];
					ans = i;
				}
			}
		}
		return ans;
	}
	static int getId(int n, vector<bool>& visit_, vector<int>& minLen)
	{
		int m = INT_MAX;
		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (!visit_[i] && m > minLen[i]) {
				m = minLen[i];
				ans = i;
			}
		}
		return ans;
	}
	static void fresh(int n, vector<bool>& visit_, vector<int>& minLen, map<pair<int, int>, int>& value, int id)
	{
		for (int i = 0; i < n; i++) {
			if (!visit_[i])minLen[i] = min(minLen[i], value[make_pair(i, id)]);
		}
	}
};

时间复杂度：O（V^2），其中V是点的数量。

力扣 1584. 连接所有点的最小费用

题目同上

const int N = 1000; //点的最大数量
int en; //点的数量
// TODO 用数组或者vector记录点的信息，id要从0开始
vector<vector<int>>p;
bool visit_[N];
int minLen[N];

int getLen(int i, int j) // 计算id为i和j的2个点的距离
{
    return abs(p[i][0] - p[j][0]) + abs(p[i][1] - p[j][1]);
}

int getStartId()
{
    int m = INT_MAX;
    int ans = 0;
    for (int i = 0; i < en; i++) {
        for (int j = 0; j < en; j++) {
            if (i != j && m > getLen(i, j)) {
                m = getLen(i, j);
                ans = i;
            }
        }
    }
    return ans;
}
void init()
{
    for (int i = 0; i < en; i++) {
        minLen[i] = INT_MAX;
        visit_[i] = false;
    }
    minLen[getStartId()] = INT_MIN;
}

int getId()
{
    int m= INT_MAX;
    int ans = 0;
    for (int i = 0; i < en; i++) {
        if (!visit_[i] && m > minLen[i]) {
            m = minLen[i];
            ans = i;
        }
    }
    return ans;
}
void fresh(int id)
{
    for (int i = 0; i < en; i++) {
        if (!visit_[i])minLen[i] = min(minLen[i], getLen(i, id));
    }
}

//计算最小生成树，结果按照边从小到大排序
vector<pair<int, int>> minCostConnectPoints2()
{
    init();
    vector<pair<int, int>>ans;
    for (int i = 0; i < en; i++) {
        int id = getId();
        for (int j = 0; j < en; j++) {
            if (visit_[j] && getLen(id, j) == minLen[id]) {
                ans.push_back(make_pair(id, j));
                break;
            }
        }
        visit_[id] = true;
        fresh(id);
    }
    return ans;
}

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        p = points;
        en = p.size();
        vector<pair<int, int>> v = minCostConnectPoints2();
        int ans = 0;
        for (pair<int, int> vi : v) {
            ans += getLen(vi.first, vi.second);
        }
        return ans;
    }
};

三，所有最小生成树的交集、并集

一个图可能有若干种不同的最小生成树，每个最小生成树其实就是一个关于边的集合，我们来求一下所有集合的交集、并集。

首先求一个最小生成树A，那么只需要找到A中哪些边属于交集，A的补集中哪些属于并集即可。

判断一条边是否属于所有最小生成树的交集，只需要删掉这条边，再求最小生成树，判断其是不是原图的最小生成树。

判断一条边是否属于所有最小生成树的并集，只需要预先指定这条边在最小生成树中，再求最小生成树，判断其是不是原图的最小生成树。

const int N = 105; //点的最大数量

int fa[N];
int find(int x)	//找祖先
{
	if (fa[x] == x)return x;
	return fa[x] = find(fa[x]);
}
void merge(int i, int j)
{
	fa[find(i)] = j;
}
bool inSameSet(int i, int j)
{
	return find(i) == find(j);
}

int en; //点的数量
vector<vector<int>>p;//用数组或者vector记录点的信息，id要从0开始

struct Edge
{
	int a;//端点id
	int b;//端点id
	int dist;
};

bool cmp(Edge a, Edge b)
{
	return a.dist < b.dist;
}
int id(Edge a)
{
	return a.a * N + a.b;
}

vector<Edge> getEdge() // 获取所有的边
{
	// TODO 根据实际情况修改
	vector<Edge> v;
	for (int i = 0; i < p.size(); i++) {
		Edge e = { p[i][0],p[i][1],p[i][2] };
		v.push_back(e);
	}
	return v;
}

//计算最小生成树，白名单w必连，黑名单b必不连
vector<Edge> minCostConnectPoints(vector<Edge>& w, vector<Edge>& b, int& treeNum, int &sumDist)
{
	vector<Edge> v = getEdge();
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < en; i++)fa[i] = i;
	sumDist = 0;
	vector<Edge>ans = w;//白名单处理
	for (auto& wi : w) {
		merge(wi.a, wi.b);
		sumDist += wi.dist;
	}
	map<int, int>mb;
	for (auto& bi : b) {
		mb[id(bi)] = 1;
	}
	for (int i = 0, j = 0; j < en - 1 && i < v.size(); i++)
	{
		if (inSameSet(v[i].a, v[i].b))continue;
		if (mb[id(v[i])])continue;//黑名单处理
		merge(v[i].a, v[i].b);
		ans.push_back(v[i]);
		sumDist += v[i].dist;
		j++;
	}
	map<int, int>m;
	for (int i = 0; i < en; i++)m[find(i)]++;
	treeNum = m.size();
	return ans;
}
//计算最小生成树，结果按照边从小到大排序，treeNum>1表示不连通,sumDist是总权重
vector<Edge> minCostConnectPoints(int& treeNum, int& sumDist)
{
	vector<Edge>w, b;
	return minCostConnectPoints(w, b, treeNum, sumDist);
}
//求所有最小生成树的交集
vector<Edge> findCriticalEdges(int n, vector<vector<int>>& edges)
{
	en = n, p = edges;
	int treeNum, sumDist;
	vector<Edge> v = minCostConnectPoints(treeNum, sumDist);
	vector<Edge>ans,w,b(1);
	for (auto& vi : v) {
		b[0] = vi;
		int treeNum2, sumDist2;
		minCostConnectPoints(w, b, treeNum2, sumDist2);
		if (treeNum2 > 1 || sumDist2 > sumDist) {
			ans.push_back(vi);
		}
	}
	return ans;
}
//求所有最小生成树的并集
vector<Edge> findPseudoCriticalEdges(int n, vector<vector<int>>& edges)
{
	en = n, p = edges;
	int treeNum, sumDist;
	vector<Edge> v = minCostConnectPoints(treeNum, sumDist);
	vector<Edge>ans=v, w(1),b;
	map<int, int>m;
	for (auto& vi : v) {
		m[id(vi)] = 1;
	}
	auto g = getEdge();
	for (auto& vi : g) {
		if (m[id(vi)])continue;
		w[0] = vi;
		int treeNum2, sumDist2;
		minCostConnectPoints(w, b, treeNum2, sumDist2);
		if (treeNum2 == 1 && sumDist2 == sumDist) {
			ans.push_back(vi);
		}
	}
	return ans;
}

力扣 1489. 找到最小生成树里的关键边和伪关键边

给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

示例 1：

输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：上图描述了给定图。
下图是所有的最小生成树。

注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。

示例 2 ：

输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

提示：

• 2 <= n <= 100
• 1 <= edges.length <= min(200, n * (n - 1) / 2)
• edges[i].length == 3
• 0 <= fromi < toi < n
• 1 <= weighti <= 1000
• 所有 (fromi, toi) 数对都是互不相同的。

关键边集合其实就是所有最小生成树的交集，伪关键边集合其实就是所有最小生成树的并集减交集。

class Solution {
public:
	vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
		auto e = findCriticalEdges(n, edges);
		vector<Edge> v = getEdge();
		vector<vector<int>>ans(2);
		map<int, int>m;
		for (auto& ei : e) {
			m[id(ei)] = 1;
		}
		for (int i = 0; i < v.size(); i++) {
			if (m[id(v[i])])ans[0].push_back(i);
		}
		e = findPseudoCriticalEdges(n, edges);
		map<int, int>m2;
		for (auto& ei : e) {
			if(!m[id(ei)])m2[id(ei)] = 1;
		}
		for (int i = 0; i < v.size(); i++) {
			if (m2[id(v[i])])ans[1].push_back(i);
		}
		return ans;
	}
};

四，带黑白名单的最小生成树

//计算最小生成树，白名单w必连，黑名单b必不连，treeNum>1表示不连通,sumDist是总权重
vector<Edge> minCostConnectPoints(vector<Edge>& w, vector<Edge>& b, int& treeNum, int& sumDist)
{
	vector<Edge> v = getEdge();
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < en; i++)fa[i] = i;
	sumDist = 0;
	vector<Edge>ans = w;//白名单处理
	for (auto& wi : w) {
		merge(wi.a, wi.b);
		sumDist += wi.dist;
	}
	map<int, int>mb;
	for (auto& bi : b) {
		mb[id(bi)] = 1;
	}
	for (int i = 0, j = 0; j < en - 1 && i < v.size(); i++)
	{
		if (inSameSet(v[i].a, v[i].b))continue;
		if (mb[id(v[i])])continue;//黑名单处理
		merge(v[i].a, v[i].b);
		ans.push_back(v[i]);
		sumDist += v[i].dist;
		j++;
	}
	map<int, int>m;
	for (int i = 0; i < en; i++)m[find(i)]++;
	treeNum = m.size();
	return ans;
}