14323: 【原4323】次小生成树
题目
题目描述
author: chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4323
题目描述
小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 E_M ，严格次小生成树选择的边集是 E_S ，那么需要满足：(value(e)表示边e的权值)
$$ \sum_{e\in E_M} value(e) < \sum_{e\in E_S} value(e) $$
这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。
输入格式
第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。 输出格式
包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)
输入输出样例
输入 #1
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
输入 #1
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
说明/提示
数据中无向图不保证无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。
zqy2018's solution
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
inline int lowbit(int x){
return x & (-x);
}
inline int modadd(int x, int y){
return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
return (!b) ? a: gcd(b, a % b);
}
int poww(int a, int b){
int res = 1;
while (b > 0){
if (b & 1) res = 1ll * res * a % MOD;
a = 1ll * a * a % MOD, b >>= 1;
}
return res;
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/
int n, m;
vector<pair<int, int> > G[100005];
pair<int, pair<int, int> > e[300005];
int fa[100005][17] = {0}, dep[100005];
int mx[100005][17], se[100005][17];
int ffa[100005], siz[100005];
ll mst;
int Find(int x){
return (ffa[x] == x ? x: (ffa[x] = Find(ffa[x])));
}
bool Union(int x, int y){
x = Find(x), y = Find(y);
if (x == y) return false;
if (siz[x] > siz[y])
ffa[y] = x, siz[x] += siz[y];
else
ffa[x] = y, siz[y] += siz[x];
return true;
}
void dfs(int cur, int f, int fw){
fa[cur][0] = f;
mx[cur][0] = fw, se[cur][0] = -INF;
dep[cur] = dep[f] + 1;
for (int j = 1; j <= 16; ++j){
int gfa = fa[cur][j - 1];
if (!fa[gfa][j - 1]) break;
fa[cur][j] = fa[gfa][j - 1];
mx[cur][j] = max(mx[cur][j - 1], mx[gfa][j - 1]);
if (mx[cur][j - 1] == mx[gfa][j - 1])
se[cur][j] = max(se[cur][j - 1], se[gfa][j - 1]);
else
se[cur][j] = min(mx[cur][j - 1], mx[gfa][j - 1]);
}
for (auto& p: G[cur]){
int v = p.first, w = p.second;
if (v == f) continue;
dfs(v, cur, w);
}
}
void upd(int u, int j, int& mxx, int& see){
if (mxx == mx[u][j])
see = max(see, se[u][j]);
else
see = min(mxx, mx[u][j]),
mxx = max(mxx, mx[u][j]);
}
pair<int, int> query(int u, int v){
if (dep[u] < dep[v]) swap(u, v);
int mxx = -INF, see = -INF;
int delta = dep[u] - dep[v];
for (int j = 16; j >= 0; --j){
if (delta < (1 << j)) continue;
delta -= (1 << j);
upd(u, j, mxx, see);
u = fa[u][j];
}
if (u == v) return make_pair(mxx, see);
for (int j = 16; j >= 0; --j){
if (fa[u][j] != fa[v][j]){
upd(u, j, mxx, see);
upd(v, j, mxx, see);
u = fa[u][j], v = fa[v][j];
}
}
upd(u, 0, mxx, see);
upd(v, 0, mxx, see);
return make_pair(mxx, see);
}
void init(){
n = read(), m = read();
REP(i, 1, m){
int u = read(), v = read(), w = read();
if (u == v) --i, --m;
else{
e[i].first = w,
e[i].second.first = u, e[i].second.second = v;
}
}
sort(e + 1, e + m + 1);
REP(i, 1, n)
ffa[i] = i, siz[i] = 1;
mst = 0;
for (int i = 1, lft = n; i <= m && lft > 1; ++i){
int u = e[i].second.first, v = e[i].second.second;
int w = e[i].first;
if (Union(u, v))
--lft,
G[u].push_back(make_pair(v, w)),
G[v].push_back(make_pair(u, w)),
mst += w;
}
dep[0] = 0;
dfs(1, 0, -INF);
}
void solve(){
ll ans = mst + INF;
REP(i, 1, m){
int u = e[i].second.first, v = e[i].second.second;
int w = e[i].first;
auto p = query(u, v);
if (w == p.first){
if (p.second != -INF) ans = min(ans, mst + w - p.second);
}else
ans = min(ans, mst + w - p.first);
}
printf("%lld\n", ans);
}
int main(){
init();
solve();
return 0;
}