【bzoj2753】[SCOI2012]滑雪与时间胶囊 最小生成树
遇到一个比较有意思的题目，写出来看看。
如果没有高度相等的点，那么就是一个有向无环图的最小树形图，贪心的让每一个点选入边中权值最小的就可以
【【bzoj2753】[SCOI2012]滑雪与时间胶囊 最小生成树】加上了高度相等的点后，变成了部分无向的最小树形图，或者说是一个分层后的最小生成树
因为，层与层之间的边都是有向的，而同一层之间的边都是无向的
如何定义层这个概念呢？高度相等的点就是一层
用一种比较巧妙的方式来做最小生成树，就可以避免处理层之间的问题
对边排序时，按照点的高度为第一关键字，边的权值为第二关键字排序
这样上一层的节点都处理完后，再处理下一层的节点，就可以把层与层之间的有向边看成无向边了
#include
#include
#include
#include
#include
#include
#define maxn 100010
#define maxm 2000010using namespace std;
struct yts
{
int x,y;
long long z;
}e[maxm];
int head[maxn],to[maxm],next[maxm];
bool vis[maxn];
int h[maxn],f[maxn],q[maxn];
int n,m,num,cnt;
long long ans;
void addedge(int x,int y,int z)
{
num++;
to[num]=y;
next[num]=head[x];
head[x]=num;
e[num]=(yts){x,y,z};
}int find(int x) {return f[x]==x?x:f[x]=find(f[x]);
}bool cmp(yts x,yts y)
{
return h[x.y]>h[y.y] || (h[x.y]==h[y.y] && x.z=h[y]) addedge(x,y,z);
if (h[y]>=h[x]) addedge(y,x,z);
}
bfs();
printf("%d ",cnt);
for (int i=1;
i<=n;
i++) f[i]=i;
sort(e+1,e+num+1,cmp);
for (int i=1;
i<=num;
i++)
{
int x=e[i].x,y=e[i].y;
if (!vis[x] || !vis[y]) continue;
int f1=find(x),f2=find(y);
if (f1!=f2) f[f1]=f2,ans+=e[i].z;
}
printf("%lld\n",ans);
return 0;
}
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长