题意就是求最小生成树 但是有一个顶点的度必须不大于k
具体的方法网上都有,但是代码写起来之复杂难以令人想象,我由于代码能力还太弱,导致只能看着别人的代码重写一遍,优化了一些部分。
1.求出除去K度点的最小生成森林,设森林数为m
2.将这m棵树与K度点用每棵树中与K度点距离最短的点相连,生成一个m度最小生成树,总答案为这个生成树的所有边长之和
3.迭代k-m次,尝试将m度生成树扩展为K度生成树,并求出最小生成树的长度
<wbr>(1)扫描k度点的所有邻接点,(注意,这是扫描的原图) 找到一个点使得(新的生成树中该点到K度点最大边的长度)与(原图中K度点到该点的距离)之差最大。 (注意,该点不能是生成树中直接与K度点相连的点)</wbr>
(2) 若(1)找出的差值不大于0,则无须继续往下找,否则,在新的生成树中连接该点到K度点,并将最大边替换掉,然后从该点开始更新最大边。此时,m度生成树变为m+1度生成树,总答案减去该差值。
(3)循环以上步骤,直到变为K度生成树或者跳出
4.打印答案
#include <iostream>
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 105
#define MAXM 100005
#define INF 1000000000
using namespace std;
struct node
{
int v, w, next;
}edge[MAXM];
struct Edge
{
int u, v, w;
Edge(){}
Edge(int a, int b, int c){u = a; v = b; w = c;}
void init(){w = 0;}
bool operator >(const Edge &a) const{
return w > a.w;
}
}mx[MAXN];//用于存储每个点到park点的最大边
int n, m, k, sum;//sum为结果
int e, head[MAXN], vis[MAXN], dis[MAXN], use[MAXN][MAXN];//head用于邻接表 vis是标记数组 dis用于求最小生成树
//use用来标记两点之间是否有边
int blocks, size[MAXN], belong[MAXN], nearvex[MAXN];//blocks表示去除park后有几个连通块 size是每个连通块的个数
//belong表示该点属于哪个连通块 nearvex用于在生成树中记录边
int point[MAXN], link[MAXN]; //point表示每个连通块中与park点最近的点 link则是该点与park点的距离
map<string, int>mp; //用于映射名字
void init()
{
e = 0, n = 1;
blocks = 0, sum = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(size, 0, sizeof(size));
memset(use, 0, sizeof(use));
for(int i = 1; i < MAXN; i++) mx[i].init();
memset(nearvex, 0, sizeof(nearvex));
mp.clear();
}
void insert(int x, int y, int w)
{
edge[e].v = y;
edge[e].w = w;
edge[e].next = head[x];
head[x] = e++;
}
int getId(char s[])
{
if(mp.find(s) == mp.end()) mp[s] = ++n;
else return mp[s];
return n;
}
void dfs(int v) //该dfs将图分成了一些连通块
{
vis[v] = 1;
size[blocks]++;
belong[v] = blocks;
for(int i = head[v]; i != -1; i = edge[i].next)
if(!vis[edge[i].v]) dfs(edge[i].v);
}
void prim(int cur) //对某个连通块求最小生成树
{
for(int i = 1; i <= n; i++) dis[i] = INF;
for(int i = 1; i <= n; i++) //设置块内某点为起点来求生成树
if(belong[i] == cur)
{
dis[i] = 0;
break;
}
for(int i = 1; i <= size[cur]; i++) //循环次数为该块的顶点数,因为这与一般的求MST略微不同
{
int mi = INF, pos = -1;
for(int j = 1; j <= n; j++)
if(nearvex[j] != -1 && mi > dis[j])
mi = dis[j], pos = j;
if(pos != -1)
{
sum += mi;
use[pos][nearvex[pos]] = use[nearvex[pos]][pos] = 1; //标记生成树中所用的边
nearvex[pos] = -1;
for(int j = head[pos]; j != -1; j = edge[j].next)
if(nearvex[edge[j].v] != -1 && dis[edge[j].v] > edge[j].w)
{
dis[edge[j].v] = edge[j].w;
nearvex[edge[j].v] = pos;
}
}
}
}
void getMax(int v, int fa, int w) //该函数用于更新新的生成树中点到park点的最大边
{
nearvex[v] = fa;
Edge t(v, fa, w);
if(mx[fa] > t) mx[v] = mx[fa];
else mx[v] = t;
for(int i = head[v]; i != -1; i = edge[i].next)
if(use[v][edge[i].v] && edge[i].v != fa) getMax(edge[i].v, v, edge[i].w); //必须是生成树中的边并且不是回边才往下搜
}
void GetMdegreeMST()
{
vis[1] = 1;
for(int i = 2; i <= n; i++) //求连通块
if(!vis[i])
{
blocks++;
dfs(i);
}
nearvex[1] = -1;
for(int i = 1; i <= blocks; i++) prim(i);
for(int i = 1; i <= n; i++) link[i] = INF;
for(int i = head[1]; i != -1; i = edge[i].next) //生成一棵m度的生成树
if(link[belong[edge[i].v]] > edge[i].w)
{
link[belong[edge[i].v]] = edge[i].w;
point[belong[edge[i].v]] = edge[i].v;
}
for(int i = 1; i <= blocks; i++) //将park点与每个连通块中与其最近的点相连,并且标记边
{
sum += link[i];
use[1][point[i]] = use[point[i]][1] = 1;
}
}
void slove()
{
int degree = blocks;
getMax(1, 0, 0); //首先从park点出发求一遍最大边
while(degree < k) //尝试迭代 k - degree次
{
int maxval = 0, pos = 0, w;
for(int i = head[1]; i != -1; i = edge[i].next) //用于找到差值最大的点
if(!use[1][edge[i].v] && mx[edge[i].v].w - edge[i].w > maxval)
{
maxval = mx[edge[i].v].w - edge[i].w, pos = edge[i].v;
w = edge[i].w;
}
if(!pos) break;
sum -= maxval;//更新答案
degree++;
use[mx[pos].u][mx[pos].v] = use[mx[pos].v][mx[pos].u] = 0;//将最大边删除
use[1][pos] = use[pos][1] = 1;
getMax(pos, 1, w);//更新最大边
}
}
int main()
{
char s1[55], s2[55];
int w;
scanf("%d", &m);
init();
mp["Park"] = 1;
for(int i = 0; i < m; i++)
{
scanf("%s%s%d", s1, s2, &w);
insert(getId(s1), getId(s2), w);
insert(getId(s2), getId(s1), w);
}
scanf("%d", &k);
GetMdegreeMST();
slove();
printf("Total miles driven: %d\n", sum);
return 0;
}
分享到:
相关推荐
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
度限制最小生成树代码 摘自POJ1639代码
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2586-Y2K Accounting Bug 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1704752
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj经典数据结构题目解题报告poj经典数据结构题目解题报告
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ题解 个人写法 线段树每个人都不一样
poj 2763 程序 线段树 LCA 2000MS AC
北大POJ1004-Financial Management 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告