1977: [BeiJing2010組隊(duì)]次小生成樹 Tree

題意：求嚴(yán)格次小生成樹

---

我為什么要單獨(dú)發(fā)這篇呢

因?yàn)橛薮赖奈也煌Q寫法最后發(fā)現(xiàn)是因?yàn)闆]開long long所以wa掉的

很簡單，次小生成樹是由mst換一條邊得到的

就是枚舉非樹邊，加入后會形成一個環(huán)，求環(huán)上的最大值和嚴(yán)格次大值與這條非樹邊換一換

用倍增可以做到O(mn)-->O(mlogn)

我寫了兩種求lca時同時求路徑上最大值/次大值的做法

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <set> using namespace std; typedef long long ll; const int N = 1e5+5, M = 3e5+5;int n, m; struct edge {int v, ne, w;} e[M<<2]; int cnt, h[N]; inline void ins(int u, int v, int w) {e[++cnt] = (edge) {v, h[u], w}; h[u] = cnt;e[++cnt] = (edge) {u, h[v], w}; h[v] = cnt; }struct meow {int u, v, w;bool operator < (const meow &r) const {return w < r.w;} } a[M];bool mark[M]; namespace mst {int fa[N];int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}ll kruskal() {for(int i=1; i<=n; i++) fa[i] = i;sort(a+1, a+1+m);int cnt = 0;ll ans = 0;for(int i=1; i<=m; i++) {int x = find(a[i].u), y = find(a[i].v);if(x != y) { //printf("use (%d, %d) %d\n", a[i].u, a[i].v, a[i].w);fa[y] = x, ans += a[i].w, mark[i] = 1;ins(a[i].u, a[i].v, a[i].w);if(++cnt == n-1) break;}}return ans;} }int deep[N], fa[N][20], vis[N]; #define fir first #define sec second pair<int, int> val[N][20]; pair<int, int> merge(pair<int, int> a, pair<int, int> b) {pair<int, int> ans;if(a.fir == b.fir) ans.fir = a.fir, ans.sec = max(a.sec, b.sec);else if(a.fir > b.fir) ans.fir = a.fir, ans.sec = max(a.sec, b.fir);else ans.fir = b.fir, ans.sec = max(a.fir, b.sec);/*ans.fir = max(a.fir, b.fir);if(a.fir == b.fir) ans.sec = max(a.sec, b.sec);else {ans.sec = min(a.fir, b.fir);ans.sec = max(ans.sec, max(a.sec, b.sec));}*/return ans; } void dfs(int u) { vis[u] = 1;for(int j=1; (1<<j)<=deep[u]; j++) {fa[u][j] = fa[fa[u][j-1]][j-1];val[u][j] = merge(val[u][j-1], val[fa[u][j-1]][j-1]);}for(int i=h[u]; i; i=e[i].ne) {int v = e[i].v;if(vis[v]) continue;deep[v] = deep[u]+1;fa[v][0] = u;val[v][0] = make_pair(e[i].w, -1);dfs(v);} }pair<int, int> lca(int x, int y) { pair<int, int> ans(-1, -1);if(deep[x] < deep[y]) swap(x, y);int bin = deep[x] - deep[y];for(int j=0; j<=17; j++)if((1<<j) & bin) ans = merge(ans, val[x][j]), x = fa[x][j];if(x == y) return ans;for(int j=17; j>=0; j--)if(fa[x][j] != fa[y][j]) {ans = merge(ans, merge(val[x][j], val[y][j]));x = fa[x][j], y = fa[y][j];}ans = merge(ans, merge(val[x][0], val[y][0]));return ans; } int lca2(int x, int y) {if(deep[x] < deep[y]) swap(x, y);int bin = deep[x] - deep[y];for(int j=0; j<=17; j++) if((1<<j) & bin) x = fa[x][j];if(x == y) return x;for(int j=17; j>=0; j--) if(fa[x][j] != fa[y][j]) x = fa[x][j], y = fa[y][j];return fa[x][0]; }pair<int, int> cal(int x, int r) {pair<int, int> ans(-1e9, -1e9);int bin = deep[x] - deep[r];for(int j=0; j<=17; j++)if((1<<j) & bin) ans = merge(ans, val[x][j]), x = fa[x][j];return ans; } int main() {freopen("in", "r", stdin);ios::sync_with_stdio(false); cin.tie(); cout.tie();cin >> n >> m;for(int i=1; i<=m; i++) {int u, v, w;cin >> u >> v >> w;a[i] = (meow) {u, v, w};}ll mn = mst::kruskal();dfs(1);int ans = 1e9+7;for(int i=1; i<=m; i++) if(!mark[i]) {int u = a[i].u, v = a[i].v, w = a[i].w;//pair<int, int> t = lca(u, v);//printf("hey (%d, %d) %d %d %d\n", u, v, w, t.fir, t.sec);int r = lca2(u, v);pair<int, int> t = merge(cal(u, r), cal(v, r));if(w > t.fir) ans = min(ans, w - t.fir);if(w == t.fir) ans = min(ans, w - t.sec);}//printf("look %d %d\n", mn, ans);cout << mn + ans; }

轉(zhuǎn)載于:https://www.cnblogs.com/candy99/p/9273044.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1977: [BeiJing2010组队]次小生成树 Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。