本文主要是介绍UVA 1151 - Buy or Build（最小生成树，二进制子集生成），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
自己实力有限。 在为了K神之后。 自己才写出来的。 二进制子集生成 又忘记了。 又去 前面翻书看的。 （P 190）
这个题。 首先要去生成 最小生成树（也就是 不同套餐的情况）
然后 用二进制子集生成。 枚举 所有套餐的选择情况。比如 套餐有 1 2 3 三种套餐 则 需要求出 所有可能的组合。 1 ， 1 2， 1 3， 1 2 3，
这样 选择每一个子集 对于每一个子集 所形成的 联通分量用并查集保存。 在 子集之外。 肯定有一些点没有链接上。
那么下一步就是 用最小生成树 把 联通分量之外的点连上（因为这样连才能保证 连上的费用是最小的）
二进制枚举子集的方法
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define ll long long
typedef unsigned long long ull;
#define maxn 2000000+10
#define INF 1<<30
int main (){ //0 1 2 3 4 的子集生成for(int i = 0; i < (1 << 5) ; i++){for(int j = 0; j < 5; j++){if(i&(1 << j))printf("%d ",j);}printf("\n");}return 0;
}
代码中都有注释
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define ll long long
typedef unsigned long long ull;
#define maxn 1000+10
#define INF 1<<30
struct po{int x,y;
};
struct point{int u, v;int cost;friend bool operator <(point a, point b){return a.cost < b.cost;}
};
po s[maxn];
int fa[maxn]; // 并查集父节点
vector <point> r; // 所有的点到点的边的长度
vector <int> l; // 这是最小生成树中的边。
vector <int> q[maxn]; // 保存的是 所有的套餐情况 其中q[i][0] 为这个套餐的费用 后面的都是套餐的点
int n,counts; // n为点数 counts 为 套餐数
int find_fa(int x){return fa[x] == x ? x : fa[x] = find_fa(fa[x]);}
int init_fa(){for(int i = 0; i <= n; i++)fa[i] = i;
}
int line(int i,int j){return (s[i].x - s[j].x)*(s[i].x - s[j].x) + (s[i].y - s[j].y)*(s[i].y - s[j].y);
}
int solve(int s){init_fa();int cost = 0;int num = 0; // 边数for(int i = 0; i < counts; i++){ // 二进制子集生成 选择可能的套餐情况 收入并查集if(s&(1 << i)){cost += q[i][0];for(int j = 2; j < q[i].size() ; j++){int x = find_fa(q[i][j]);int y = find_fa(q[i][j-1]);if(x != y){fa[y] = x;num ++;}}}}for(int i = 0; num < n - 1; i++){ // 在所生成的子集中。 按照最小生成树 补边int l_ = l[i];int x = find_fa(r[l_].u);int y = find_fa(r[l_].v);int c = r[l_].cost;if(x != y){cost += c;num++;fa[x] = y;}}return cost;
}
int main (){int num;int b = 0;scanf("%d",&num);while(num--){if(b)printf("\n");b++;scanf("%d%d",&n,&counts);r.clear();l.clear();for(int i = 0; i <= counts; i++)q[i].clear();for(int i = 0; i < counts; i++){int x;scanf("%d",&x);int mo;for(int j = 0; j <= x; j++){scanf("%d",&mo);q[i].push_back(mo); // q 第一项代表 费用。 后面代表点。}}for(int i = 1; i <= n; i++)scanf("%d%d",&s[i].x,&s[i].y);init_fa();for(int i = 1; i <= n-1; i++){for(int j = i+1; j <= n; j++){point pp;pp.u = i,pp.v = j,pp.cost = line(i,j);r.push_back(pp);// printf("%d %d %d\n",i,j,line(i,j));}}sort(r.begin(),r.end());int len = r.size();int minn = 0;for(int i = 0; i < len; i++){ // 并查集形成 最小生成树的 集合int uu = r[i].u;int vv = r[i].v;int x = find_fa(uu);int y = find_fa(vv);if(x != y){fa[x] = y;minn += r[i].cost;l.push_back(i); // 求出 最小生成树的边的集合}}int cost_min = minn; // 没有套餐的时候for(int i = 1; i < (1 << counts); i++){ // 枚举选择 所有套餐的子集int minx = solve(i);cost_min = min(minx, cost_min);}printf("%d\n",cost_min);}return 0;
}
这篇关于UVA 1151 - Buy or Build（最小生成树，二进制子集生成）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
