次小生成树

C++14(g++5.4) 解法, 执行用时: 699ms, 内存消耗: 36020K, 提交时间: 2020-01-21 19:05:33

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+1;
const int MAXM = 1e5+1;

int N, M;
struct Edge {
  int u, v, w;
  bool inMst;
};

int p[MAXN];
void init() {
  for (int i = 1; i <= N; i++) p[i] = i;
}
int find(int x) { return p[x] = p[x] == x? x: find(p[x]);}
vector<pair<int, int>> G[MAXN];
int H[MAXN];
int F[MAXN][20];
int V1[MAXN][20];
int V2[MAXN][20];


int get_v(int x, int i, int w) {
  if (V1[x][i] != w) return V1[x][i];
  return V2[x][i];
}
void dfs_lca(int s, int f, int w) {
  F[s][0] = f, H[s] = H[f] + 1;
  V1[s][0] = w, V2[s][0] = -0x3f3f3f3f;
  for (int i = 0; i < 19; i++) {
    int k = F[s][i];
    F[s][i+1] = F[k][i];
    V1[s][i+1] = V1[s][i], V2[s][i+1] = V2[s][i];
    if (V1[k][i] > V1[s][i])  V2[s][i+1] = max(V1[s][i+1], V2[k][i]), V1[s][i+1] = V1[k][i];
    else if (V1[k][i] < V1[s][i]) V2[s][i+1] = max(V1[k][i], V2[s][i]), V1[s][i+1] = V1[s][i];
    else V2[s][i+1] = max(V2[k][i], V2[s][i]), V1[s][i+1] = V1[s][i];
  }
  for (auto it: G[s]) if (it.first != f) dfs_lca(it.first, s, it.second);
}
int get(int x, int y, int w) {
  int ans = -0x3f3f3f3f;
  if (H[x] < H[y]) swap(x, y);
  for (int i = 19; i >= 0; i--) if (H[F[x][i]] >= H[y]) {
    ans = max(ans, get_v(x, i, w));
    x = F[x][i];
  }
  if (x == y) return ans;
  for (int i = 19; i >= 0; i--) if (F[x][i] != F[y][i]) {
    ans = max(ans, get_v(x, i, w));
    ans = max(ans, get_v(y, i, w));
    x = F[x][i], y = F[y][i];
  }
  ans = max(ans, get_v(x, 0, w));
  ans = max(ans, get_v(y, 0, w));
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> N >> M;
  vector<Edge> edges(M); for(auto &e: edges) cin>> e.u >> e.v >> e.w;
  sort(edges.begin(), edges.end(), [](const Edge &l, const Edge &r) {
    return l.w < r.w;
  });
  init();
  int cnt = 0;
  long long mst = 0;
  for (auto &e: edges) {
    int x = e.u, y = e.v;
    int px = find(x), py = find(y);
    if (px == py) continue;
    p[px] = py;
    G[x].push_back({y, e.w});
    G[y].push_back({x, e.w});
    e.inMst = true;
    mst += e.w;
    if (++cnt == N - 1) break;
  }
  dfs_lca(1, 0, 0);

  long long ans = 0x3f3f3f3f3f3f3f3f;
  for (auto &e: edges) if (!e.inMst) {
    int t = get(e.u, e.v, e.w);
    if (t == -0x3f3f3f3f) continue;
    ans = min(ans, mst + e.w - t);
  }
  cout << ans << endl;
}

C++(clang++11) 解法, 执行用时: 274ms, 内存消耗: 34912K, 提交时间: 2020-11-04 20:16:13

#include<bits/stdc++.h>
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int nn=101104,mm=301104;
int n,m,ans=INT_MAX,fa[nn],dep[nn];
int f[nn][20],g[nn][20][2];
long long sum;
vector<pii>son[nn];
struct edge{int x,y,z;}e[mm];
bool cmp(edge a,edge b){return a.z<b.z;}
int get(int i){return fa[i]==i?i:fa[i]=get(fa[i]);}
void up(int a,int b,int c,int d,int&x,int&y){
	x=max(a,b);
	if(a==b)y=max(c,d);
	else if(a<b)y=max(a,d);
		else y=max(b,c);
}void dfs(int u){
	dep[u]++;
	for(int i=0;f[u][i];i++)
		f[u][i+1]=f[f[u][i]][i],
		up(g[u][i][0],g[f[u][i]][i][0],
		g[u][i][1],g[f[u][i]][i][1],
		g[u][i+1][0],g[u][i+1][1]);
	for(int i=0,v;i<(int)son[u].size();i++)
		if((v=son[u][i].first)!=f[u][0])
			f[v][0]=u,g[v][0][0]=son[u][i].second,
			dep[v]=dep[u],dfs(v);
}int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=0;i<m;i++)
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
	sort(e,e+m,cmp);
	for(int i=0,x,y,z;i<m;i++)
		if(get(x=e[i].x)!=get(y=e[i].y))
			fa[get(x)]=get(y),sum+=(z=e[i].z),
			son[x].eb(mp(y,z)),son[y].eb(mp(x,z));
	dfs(1);for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=0,x,y,a,b,d;i<m;i++)
		if(get(x=e[i].x)==get(y=e[i].y)){
			if(dep[x]<dep[y])swap(x,y);
			a=b=0,d=dep[x]-dep[y];
			for(int j=0;d;d>>=1,j++)if(d&1)
				up(a,g[x][j][0],b,g[x][j][1],a,b),x=f[x][j];
			if(x!=y){
				for(int j=18;j>=0;j--)if(f[x][j]!=f[y][j])
					up(a,g[x][j][0],b,g[x][j][1],a,b),
					up(a,g[y][j][0],b,g[y][j][1],a,b), 
					x=f[x][j],y=f[y][j];
				up(a,g[x][0][0],b,g[x][0][1],a,b),x=f[x][0],
				up(a,g[y][0][0],b,g[y][0][1],a,b),y=f[y][0];
			}if(e[i].z>a)ans=min(ans,e[i].z-a);
			else if(b)ans=min(ans,e[i].z-b);
		}else fa[get(x)]=get(y);
	return printf("%lld",sum+ans),0;
}

详情