文章
25
粉丝
0
获赞
0
访问
68483
度受限的最小生成树:
给定一张N个点,M个边的无向图,求出无向图的一颗最小生成树,但是我们要求一号节点的入度不可以超过给定的整数S
也就是一个最小生成树,要求它的一号节点,最多只能和S个节点相连.
——————————————————————————————————————————————————————————
(1)将一个无向图去掉根节点(编号为1)后得到的连通块:
bool vis[dot_num] = { false };//记录每个节点加入连通块的情况
int cnt = 0;//连通块的数量
for (int i = 1; i <= dot_num; i++){
if (!vis[i]){
cnt++;
vis[i] = cnt;
dfs(i);
}
}
void dfs(int x){
for (int j = 2; j <= dot_num; j++){
if (G[x][j] && !vis[j]){
vis[j] = cnt;
dfs(j);
}
}
}
-------------------------------------------------------------------------------------
#include<iostream>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
const int N = 1010;
int edge_num, dot_num, n, m, cnt, root;//cnt;联通快的数量
int father[N], G[50][50], dis[50][50];
map<string,int>q;//将字符串输入映射成节点数字编号
map<pair<int,int>, bool>qq;//记录边是否在生成树中
bool vis[N];//连通块的编号
int degree;//受限制的度
int findfather(int x){
while (x != father[x]){
x = father[x];
}
return father[x];
}
struct edge{
int from, to, weight;
bool operator <(const edge b)const{
return weight < b.weight;
}
}g[N];
inline int kruskal(){//将除度受限根节点1的剩余其它所有节点求最小生成树
sort(g + 1, g + edge_num + 1);
int ans = 0;
for (int i = 1; i <= edge_num; i++){
int x = findfather(g[i].from); int y = findfather(g[i].to);
if (x == 1 || y == 1 || x == y){ //除节点1和x,y若在同一个联通块
continue;
}
father[x] = y;
ans += g[i].weight;
//标记该边在最小生成树中
qq[{g[i].from, g[i].to}] = true; qq[{g[i].to, g[i].from}] = true;
}
return ans;//最小生成树的权值和
}
//划分连通块
void dfs(int x){
for (int j = 2; j <= dot_num; j++){
if (G[x][j] && !vis[j]){
vis[j] = cnt;
dfs(j);
}
}
}
struct node{
int u, v, d;
inline void init(){
u = v = 0;
d = -1;
}
}dp[N];
void dfs(int now, int last){
for (int i = 2; i <= n; i++){
if (last == i || !qq[{now,i}]){//如果最小生成树中没有这条边
continue;
}
if (dp[i].d == -1){
if (dp[now].d > G[now][i]){
dp[i] = dp[now];
}
else{
dp[i].u = now;
dp[i].v = i;
dp[i].d = G[now][i];
}
}
dfs(i, now);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
fill(G[0], G[0] + 50 * 50, 0);
memset(vis, false, sizeof vis);
cin >> n;
for (int i = 1; i <= n; i++){
father[i] = i;
}
q["Park"] = 1; dot_num++;//根节点,即度受限的点root数字编号为1
string a, b; int c;
for (int i = 0; i < n; i++){
cin >> a >> b >> c;
if (!q[a]){ //将字符节点映射成数字编号
q[a] = ++dot_num;
}
if (!q[b]){
q[b] = ++dot_num;
}
//加边存入邻接矩阵
G[q[a]][q[b]] = G[q[b]][q[a]] = c;
g[++edge_num].from = q[a]; g[edge_num].to = q[b]; g[edge_num].weight = c;//用于kruskal求最小生成树
}
cin >> degree;
//除去根节点后将图划分成连通块
for (int i = 2; i <= dot_num; i++){
if (!vis[i]){
cnt++;
vis[i] = cnt;
dfs(i);
}
}
int res = kruskal();
//将每一个连通块与1相连
for (int i = 1; i <= cnt; i++){
int now = 0x3f3f3f3f, index = 0;
for (int j = 2; j <= dot_num; j++){//找到与1相连边最小的点
if (vis[j] == i){
if (now > G[1][j] && G[1][j]){
now = G[i][j];
index = j;
}
}
}
res += now;
qq[{1, index}] = qq[{index, 1}] = true;
}
int t = cnt;
while (degree > t){
degree--;
for (int i = 1; i <= n; i++){
dp[i].init();
}
dfs(1, -1);
int now = 0, idx = 0;
for (int j = 2; j <= dot_num; j++){
if (G[1][j] && now < (dp[j].d - G[1][j])){
now = dp[j].d - G[1][j];
idx = j;
}
}
if (now <= 0){ break; }//不会使最小生成树权值更小,1的度只需维持比degree小即可
res -= now;
qq[{dp[idx].u, dp[idx].v}] = qq[{dp[idx].v, dp[idx].u}] = false;
qq[{1, idx}] = qq[{idx, 1}] = true;
}
cout << "Total miles driven: " << res << endl;
return 0;
}
登录后发布评论
暂无评论,来抢沙发