【学习笔记】浅谈最小生成树及重构树
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
定义
生成树
一个连通图的生成树是一个极小的连通子图它包含图中全部的 n n n 个顶点但只有构成一棵树的 n − 1 n-1 n−1 条边。
最小生成树
其实就是一个图中最小的一个生成树
所谓一个 带权图 的最小生成树就是原图中边的权值最小的生成树 所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。
prim 算法
先讲我不怎么会的
有一说一
P
r
i
m
Prim
Prim 确实和
d
i
j
k
s
t
r
a
dijkstra
dijkstra 很像而且似乎都可以用堆优化
先讲一下 P r i m Prim Prim 最核心的思想部分
对于任意一个顶点 v v v 连接到该顶点的所有边中的一条最短边 ( v , v j ) (v, v_j) (v,vj) 必然属于最小生成树即任意一个属于最小生成树的连通子图从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树
所以自然就是和 d i j k s t r a dijkstra dijkstra 一样去不断的松弛找最小边噜
Code
你怎么知道我又去题解区了
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define maxn 5005
#define maxm 200005
struct edge{
int v,w,next;
}e[maxm<<1];
int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;
bool vis[maxn];
void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void init(){
cin >> n >> m;
for(int i=1,u,v,w;i<=m;++i){
cin >> u >> v >> w;
add(u,v,w),add(v,u,w);
}
}
int prim(){
for(int i=2;i<=n;++i){
dis[i]=inf;
}
for(int i=head[1];i;i=e[i].next){
dis[e[i].v]=min(dis[e[i].v],e[i].w);
}
while(++tot<n){
int minn=inf;
vis[now]=1;
for(re int i=1;i<=n;++i){
if(!vis[i]&&minn>dis[i]){
minn=dis[i];
now=i;
}
}
ans+=minn;
for(int i=head[now];i;i=e[i].next){
int v=e[i].v;
if(dis[v]>e[i].w&&!vis[v]){
dis[v]=e[i].w;
}
}
}
return ans;
}
int main(){
init();
printf("%d",prim());
return 0;
}
你怎么知道我没编译过这个代码
又被你懂完了
Borůvka 算法
emmm感觉这个算法挺冷门的罢
放个大佬博客链接 逃
这个B开头的算法基本思想就是对于现在存在的每个联通快都找一个离他最近的块连起来合并然后处理一下细节Maybe 就可以结束了
这个算法的优势就在于每一次合并之后联通快个数都会减半也就是说一共只需要进行 l o g N log N logN 次合并这是 P r i m Prim Prim 和 k r u s k a l kruskal kruskal 难以达到的所以只要想考察这个算法就与这个特性密切相关。比如说 this
个人感觉这个算法应该考到概率不大不过这种合并的思想值得借鉴
Code
你猜猜为什么没有代码
显然是因为我没打
Kruskal
终于写到我会的东西了喜
如果你想要学习 K r u s k a l Kruskal Kruskal 你需要学会的是
- 并查集
- 好像就没了
先讲一下算法流程
首先对所有的边进行排序然后从小到大枚举每一条边如果这条边所连的两个端点没有在同一个联通块内那就把这两个块联通起来最后搞一个变量记录一下加了多少边就好力不会还有人想不到在一共加了 n − 1 n-1 n−1 条边的时候程序就跑完了吧
Code
来看看我丑陋的代码惊我模版竟然拿prim过的
void kruskal(){
for(int i =1;i <= n; i++) ff[i] = i;
sort(e+1,e+1+m,cmp);
for(int i =1;i <= m; i++){
int fu = get(e[i].u),fv = get(e[i].v);
if(fu != fv){
fa[fu] = fv;
cnt++;
sum += e[i].val;
}
}
}
反正大致就长这样说白了就是懒得打
谈谈重构树
重构树尊的是个好东西他可以用来处理路径权瓶颈的问题
说详细点就是求两点路径的最小最大值或者最大最小值又或者求只能走权值小于等于某个值或大于等于某个值的路径
建议在这里看完基本原理之后切题前学一下倍增和lca
这题大意就是求两点间路径权值最小边最大值诶最小边最大值是不是可以二分试一下
基本思想
众所周知重构树也叫 k r u s k a l kruskal kruskal重构树
其核心步骤就是先把边进行排序枚举每一条边如果两条边不属于同一个集合就新建一个节点 其权值就是边权把两个节点分别作为新节点的两个孩子
进行这样的重构树之后不难发现左右节点的后代节点的权值都是小于大于这个节点的所以像货车运输这题就可以直接进行重构树然后找两个节点的 L C A LCA LCA
Code
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
const int N = 2e4+10;
const int M = 1e5+10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
using namespace std;
int n, m;
int h[N],ne[M],node[M],idx = 0;
void add(int u, int v){
node[++idx] = v;
ne[idx] = h[u];
h[u] = idx;
}
int val[N];
struct NODE{
int u,v,w;
}e[M];
bool cmp(NODE a, NODE b){
return a.w > b.w;
}
int fa[N],cnt,ff[N];
int get(int x){
return x == ff[x] ? x: ff[x] = get(ff[x]);
}
int siz[N],son[N],tp[N],dep[N];
void dfs1(int pos,int f){
siz[pos] = 1;
for(int i = h[pos];i;i=ne[i]){
int to = node[i];
if(to == f) continue;
dep[to] = dep[pos]+1;
// cout << to << ' ' << dep[to] << endl;
fa[to] = pos;
dfs1(to,pos);
siz[pos] += siz[to];
if(siz[to] > siz[son[pos]]) son[pos] = to;
}
}
void dfs2(int pos,int top){
tp[pos] = top;
if(son[pos]) dfs2(son[pos],top);
for(int i = h[pos];i;i=ne[i]){
int to = node[i];
if(to == fa[pos] || to == son[pos]){
continue;
}
dfs2(to,to);
}
}
void kruskal(){
for(int i =1;i <= n; i++) ff[i] = i;
sort(e+1,e+1+m,cmp);
for(int i =1;i <= m; i++){
int fu = get(e[i].u),fv = get(e[i].v);
if(fu != fv){
val[++cnt] = e[i].w;
ff[cnt] = ff[fu] = ff[fv] = cnt;
add(fu,cnt);
add(cnt,fu);
add(fv,cnt);
add(cnt,fv);
// cout << cnt << endl;
}
}
for(int i = 1; i<= cnt;i++){
if(!siz[i]){
int f = get(i);
dfs1(f,0);
dfs2(f,f);
}
}
}
int LCA(int x, int y){
while(tp[x] != tp[y]){
if(dep[tp[x]] < dep[tp[y]]) y = fa[tp[y]];
else x = fa[tp[x]];
// cout << dep[y] << endl;
}
return dep[x] < dep[y] ? x: y;
}
int main(){
cin >> n >> m;
for(int i =1; i<= m; i++){
cin >> e[i].u >> e[i].v >> e[i].w;
}
cnt = n;
int t;
cin >> t;
kruskal();
while(t--){
int x, y;
cin >> x >> y;
// cout << LCA(x,y) << endl;
if(get(x) != get(y)) puts("-1");
else cout << val[LCA(x,y)] << endl;
}
return 0;
}
这里补一张图
最后再放几道练习题
代码等我写了再补上罢
P2245 星际导航
#include <bits/stdc++.h>
const int N = 2e5+10;
const int M = 6e5+10;
using namespace std;
int n, m;
int h[N],ne[M],node[M],idx = 0;
void add(int u, int v){
node[++idx] = v;
ne[idx] = h[u];
h[u] = idx;
}
int fa[N];
int get(int x){
return x == fa[x] ? x : fa[x] = get(fa[x]);
}
int f[N][25],dep[N];
void dfs(int pos, int ff){
dep[pos] = dep[ff]+1;
f[pos][0] = ff;
for(int i = 1; i <= 20; i++){
f[pos][i] = f[f[pos][i-1]][i-1];
}
for(int i = h[pos]; i; i = ne[i]){
int t = node[i];
if(t == ff) continue;
dfs(t,pos);
}
}
int LCA(int x, int y){
if(dep[x] < dep[y]) swap(x,y);
for(int i = 20; i >= 0; i--){
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = 20; i >= 0; i--){
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
struct edge{
int u, v, w;
}e[M];
bool cmp(edge x, edge y){
return x.w < y.w;
}
int val[N];
void kruskal(){
int cnt = n,tot=0;
for(int i = 1; i <= 2*n; i++) fa[i] = i;
sort(e+1,e+1+m,cmp);
for(int i = 1; i <= m;i++){
int fu = get(e[i].u),fv = get(e[i].v);
if(fu != fv){
fa[fu] = fa[fv] = ++cnt;
val[cnt] = e[i].w;
add(cnt,fu),add(cnt,fv);
tot++;
}
if(tot==n-1) break;
}
for(int i = 1; i <= n; i++){
if(!dep[i]){
dfs(get(i),0);
}
}
}
int main(){
cin >> n >> m;
for(int i = 1;i <= m; i++){
cin >> e[i].u >> e[i].v >> e[i].w;
}
kruskal();
int q;
cin >> q;
while(q--){
int x,y;
cin >> x >> y;
if(get(x) != get(y)){
cout << "impossible" << endl;
continue;
}
int lca = LCA(x,y);
// cout << lca << " ";
cout << val[lca] << endl;
}
return 0;
}
Power Tree
#include <bits/stdc++.h>
#define int long long
const int N = 2e5+10;
using namespace std;
struct edge{
int u, v, w,pos;
}e[N];
int m = 0;
bool cmp(edge x, edge y){
return x.w < y.w;
}
bool ans[N];
int val[N];
int h[N],ne[N<<1],node[N<<1],idx = 0;
void add(int u, int v){
node[++idx] = v;
ne[idx] = h[u];
h[u] = idx;
}
int L[N],R[N],cur = 0;
void dfs(int pos, int fa){
bool f = 1;
L[pos] = 1e9;
for(int i = h[pos];i;i = ne[i]){
int to = node[i];
if(to == fa) continue;
f = 0;
dfs(to,pos);
L[pos] = min(L[pos],L[to]),R[pos] = max(R[pos],R[to]);
}
if(f) L[pos] = R[pos] = ++cur;
e[++m].u = L[pos],e[m].v = R[pos]+1,e[m].w = val[pos],e[m].pos = pos;
}
int fa[N];
int get(int x){
return fa[x] == x ? fa[x] : fa[x] = get(fa[x]);
}
int n;
int tot = 0;
int sum = 0;
void kruskal(){
for(int i = 1; i <= n+1; i++) fa[i] = i;
sort(e+1,e+1+m, cmp);
for(int l = 1; l <= n;){
int r=l;
while(r+1 <= n && e[r].w == e[r+1].w){
r++;
}
for(int i = l; i <= r; i++){
if(get(e[i].u) != get(e[i].v)){
ans[e[i].pos] = 1;
tot++;
}
}
for(int i = l; i <= r; i++){
int fu = get(e[i].u),fv = get(e[i].v);
if(fu != fv){
fa[fu] = fv;
sum += e[i].w;
}
}
l = r+1;
}
cout << sum <<" " << tot << endl;
}
signed main(){
cin >> n;
for(int i = 1;i <= n; i++){
cin >> val[i];
}
for(int i = 1;i <n; i++){
int u, v;
cin >> u >> v;
add(u,v),add(v,u);
}
dfs(1,0);
kruskal();
for(int i = 1;i <= n; i++){
if(ans[i]) cout << i << ' ';
}
return 0;
}
P4768 [NOI2018] 归程
#include <bits/stdc++.h>
#define int long long
const int N = 1e6+10;
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void write(int x){
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n, m;
int h1[N], ne1[N], node1[N],val1[N];
int idx1 = 0;
void add1(int u, int v, int w){
node1[++idx1] = v;
val1[idx1] = w;
ne1[idx1] = h1[u];
h1[u] = idx1;
}
int h2[N], ne2[N], node2[N];
int idx2 = 0;
void add2(int u, int v){
node2[++idx2] = v;
ne2[idx2] = h2[u];
h2[u] = idx2;
}
struct Node{
int ans,h;
}node[N];
struct edge{
int u,v,h;
}e[N];
bool cmp(edge x, edge y){
return x.h > y.h;
}
int dis[N];
bool vis[N];
void dij(){
fill(dis,dis+n+1,1e18);
fill(vis,vis+1+n,0);
dis[1] = 0;
priority_queue<pair<int,int> > q;
q.push(make_pair(-dis[1],1));
while(!q.empty()){
int t = q.top().second;
q.pop();
if(vis[t]) continue;
vis[t] = 1;
for(int i = h1[t]; i; i = ne1[i]){
int v = node1[i];
if(dis[v] > dis[t]+val1[i]){
dis[v] = dis[t] + val1[i];
q.push(make_pair(-dis[v],v));
}
}
}
for(int i =1 ;i <= n; i++){
node[i].ans = dis[i];
}
}
int fa[N];
int get(int x){
return fa[x] == x ? x : fa[x] = get(fa[x]);
}
int kruskal(){
int cnt = n,tot = 0;
for(int i =1; i <= n*2; i++) fa[i] = i;
sort(e+1,e+1+m, cmp);
for(int i =1 ; i <= m; i++){
int u = e[i].u, v = e[i].v, h = e[i].h;
int fu = get(u),fv = get(v);
if(fu != fv){
fa[fu] = fa[fv] = ++cnt;
node[cnt].h = h;
add2(cnt,fu),add2(cnt,fv);
tot++;
}
if(tot == n-1) return cnt;
}
return cnt;
}
int dep[N],f[N][25];
void dfs(int pos, int father){
dep[pos] = dep[father]+1;
f[pos][0] = father;
for(int i = 1; i <= 19; i++){
f[pos][i] = f[f[pos][i-1]][i-1];
}
for(int i = h2[pos]; i; i= ne2[i]){
int to = node2[i];
dfs(to,pos);
node[pos].ans = min(node[pos].ans,node[to].ans);
}
}
void solve(){
//return;
n=read(),m=read();
fill(h1,h1+n+1,0);
fill(h2,h2 + n*2+1, 0);
idx1 = idx2 = 0;
for(int i = 0; i <= n*2+1; i++) node[i].ans = 1e18;
//return;
memset(f,0,sizeof f);
memset(e,0,sizeof e);
for(int i = 1; i <= m; i++){
int u, v, l, a;
u=read(), v=read(), l=read() , a=read();
add1(u,v,l);
add1(v,u,l);
e[i].u = u,e[i].v = v,e[i].h = a;
}
//return;
dij();
//return;
int cnt = kruskal();
dfs(cnt,0);
//return;
int q, k, s;
int lastans = 0;
q=read() ,k =read(), s = read();
while(q--){
int v0,p0;
v0 =read(), p0 = read();
int st = (v0+k*lastans-1)%n+1,p = (p0+k*lastans)%(s+1);
for(int i = 19; i >=0 ; i--){
if(dep[st] - (1 << i) > 0 && node[f[st][i]].h > p) st = f[st][i];
}
write(lastans = node[st].ans);
puts("");
}
}
signed main(){
//freopen("return6.in","r",stdin);
//return 0;
int t;
t = read();
while(t--) solve();
return 0;
}
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |