生活随笔
收集整理的這篇文章主要介紹了
MST(最小生成树)上的确定性和存在性问题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目1：
給定一個n個點(diǎn)m條邊的連通圖，保證沒有自環(huán)和重邊。對于每條邊求出,在其他邊權(quán)值不變的情況下,它能取的最大權(quán)值，使得這條邊在連通圖的所有最小生成樹上。假如最大權(quán)值為無限大，則輸出-1。
題解：
先求出圖的一棵最小生成樹：
對于不在樹上的邊(x,y)， 它的權(quán)值只要小于樹上x到y(tǒng)路徑中任意一條邊就可以代替這條邊。
對于在樹上的邊(x,y)，可以先預(yù)處理出所有兩端在x到y(tǒng)路徑上的不在樹上的邊的最小值。它的權(quán)值一定要小于最小值。
路徑max和min都可以用倍增求。
時間復(fù)雜度O(nlogn)
#include<bits/stdc++.h>
using namespace std
;
const int N
=2e5+5;
inline int read(){int x
=0,f
=1;char ch
=getchar();while(!isdigit(ch
)){if(ch
=='-')f
=-1;ch
=getchar();}while(isdigit(ch
)){x
=x
*10+ch
-'0';ch
=getchar();} return x
*f
;
}
int n
,m
,cnt
=0,head
[N
];
int vis
[N
],ans
[N
];
int fa
[N
],dep
[N
],id
[N
];
int f
[N
][20],maxn
[N
][20];
struct data{int x
,y
,dis
,id
;
}a
[N
];
struct Edge{int v
,w
,nxt
,id
;
}edge
[N
<<1];
void add_edge(int u
,int v
,int w
,int id
){edge
[++cnt
].v
=v
;edge
[cnt
].w
=w
;edge
[cnt
].id
=id
;edge
[cnt
].nxt
=head
[u
];head
[u
]=cnt
;
}
int find(int x
){if(fa
[x
]==x
) return fa
[x
];else return fa
[x
]=find(fa
[x
]);
}
bool cmp(data a
,data b
){return a
.dis
<b
.dis
;
}
void build(){sort(a
+1,a
+m
+1,cmp
);for(int i
=1;i
<=n
;i
++) fa
[i
]=i
;for(int i
=1;i
<=m
;i
++){int x
=a
[i
].x
;int y
=a
[i
].y
;if(find(x
)!=find(y
)){fa
[find(x
)]=find(y
);vis
[a
[i
].id
]=1;add_edge(x
,y
,a
[i
].dis
,a
[i
].id
);add_edge(y
,x
,a
[i
].dis
,a
[i
].id
);}}
}
void dfs(int u
){for(int i
=1;i
<=18;i
++){f
[u
][i
]=f
[f
[u
][i
-1]][i
-1];maxn
[u
][i
]=max(maxn
[u
][i
-1],maxn
[f
[u
][i
-1]][i
-1]);}for(int i
=head
[u
];i
;i
=edge
[i
].nxt
){int v
=edge
[i
].v
;int w
=edge
[i
].w
;if(v
==f
[u
][0]) continue;dep
[v
]=dep
[u
]+1;id
[v
]=edge
[i
].id
;f
[v
][0]=u
;maxn
[v
][0]=w
;dfs(v
);}
}
void solve(int x
,int y
,int dis
){x
=find(x
);while(dep
[x
]>dep
[y
]){ans
[id
[x
]]=min(ans
[id
[x
]],dis
-1);int k
=find(f
[x
][0]);fa
[x
]=k
;x
=find(x
);}
}
int get(int x
,int y
,int &lca
){int ans
=0;if(dep
[x
]<dep
[y
]) swap(x
,y
);for(int i
=18;i
>=0;i
--)if(dep
[f
[x
][i
]]>=dep
[y
]){ans
=max(ans
,maxn
[x
][i
]);x
=f
[x
][i
];}if(x
==y
){lca
=x
;return ans
;}for(int i
=18;i
>=0;i
--){if(f
[x
][i
]!=f
[y
][i
]){ans
=max(ans
,maxn
[x
][i
]);ans
=max(ans
,maxn
[y
][i
]);x
=f
[x
][i
],y
=f
[y
][i
];}}lca
=f
[x
][0];return max(ans
,max(maxn
[x
][0],maxn
[y
][0]));
}
int main(){n
=read();m
=read();for(int i
=1;i
<=m
;i
++){a
[i
].x
=read();a
[i
].y
=read();a
[i
].dis
=read();ans
[i
]=2e9; a
[i
].id
=i
;}build();dfs(1);for(int i
=1;i
<=n
;i
++) fa
[i
]=i
;for(int i
=1;i
<=m
;i
++){if(!vis
[a
[i
].id
]){int x
=a
[i
].x
,y
=a
[i
].y
,z
;ans
[a
[i
].id
]=get(x
,y
,z
)-1;solve(x
,z
,a
[i
].dis
);solve(y
,z
,a
[i
].dis
);}}for(int i
=1;i
<=m
;i
++){if(ans
[i
]==2e9) printf("-1 ");else printf("%d ",ans
[i
]);}
}
題目2：
題解：
題目的操作其實可以看成給一條邊權(quán)值加一
(u[lab],v[lab])這條邊會被算到最小生成樹里面，只有在權(quán)值小于等于它的邊加完后，u[lab]和v[lab]不在一個連通塊內(nèi)。
我們把權(quán)值小于等于l[lab]的圖建出來，現(xiàn)在問題變成，你可以用l[lab]?l[i]+1的代價砍掉一些邊使得u[lab]和v[lab]不連通，最小割就好了。
題目3：
給定一個有n個點(diǎn)，m條邊的無向連通圖，每條邊有邊權(quán)。 定義一次操作為：選擇一條圖中的邊，并將其權(quán)值+1。
試求最小的操作次數(shù)，使得操作后的圖的最小生成樹是唯一的。
題解
總結(jié)
以上是生活随笔為你收集整理的MST(最小生成树)上的确定性和存在性问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
