NC51257. 次小生成树
描述
输入描述
第一行包含两个整数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
输出:
11
C++14(g++5.4) 解法, 执行用时: 472ms, 内存消耗: 63608K, 提交时间: 2020-08-22 16:08:09
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=3e5+5;
int n,m,t,fa[N],d[N],f[N][20],g[N][20][2];
bool st[M];
vector<pair<int,int>> G[N];
struct E {
int u,v,w;
E() {}
E(int u,int v,int w):u(u),v(v),w(w) {}
bool operator < (const E &a) const {
return w<a.w;
}
}e[M];
int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int kruskal() {
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m);
int res=0;
for(int i=1;i<=m;i++) {
int tx=find(e[i].u),ty=find(e[i].v);
if(tx==ty) continue;
st[i]=true;
fa[tx]=ty;
res+=e[i].w;
G[e[i].u].push_back(make_pair(e[i].v,e[i].w));
G[e[i].v].push_back(make_pair(e[i].u,e[i].w));
}
return res;
}
void bfs() {
queue<int> q;
q.push(1);
d[1]=0;
while(!q.empty()) {
int u=q.front();
q.pop();
for(auto x:G[u]) {
int v=x.first;
if(v==f[u][0]) continue;
d[v]=d[u]+1;
f[v][0]=u;
for(int i=1;i<=t;i++) f[v][i]=f[f[v][i-1]][i-1];
g[v][0][0]=x.second;
g[v][0][1]=0;
for(int j=1;j<=t;j++) {
g[v][j][0]=max(g[v][j-1][0],g[f[v][j-1]][j-1][0]);
if(g[v][j-1][0]==g[f[v][j-1]][j-1][0]) g[v][j][1]=max(g[v][j-1][1],g[f[v][j-1]][j-1][1]);
else if(g[v][j-1][0]<g[f[v][j-1]][j-1][0]) g[v][j][1]=max(g[v][j-1][0],g[f[v][j-1]][j-1][1]);
else if(g[v][j-1][0]>g[f[v][j-1]][j-1][0]) g[v][j][1]=max(g[v][j-1][1],g[f[v][j-1]][j-1][0]);
}
q.push(v);
}
}
}
int LCA(int a,int b) {
if(d[a]>d[b]) swap(a,b);
for(int i=t;i>=0;i--) if(d[f[b][i]]>=d[a]) b=f[b][i];
if(a==b) return a;
for(int i=t;i>=0;i--) if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
return f[a][0];
}
pair<int,int> calc(int a,int b) {
pair<int,int> res(0,0);
for(int i=t;i>=0;i--)
if(d[f[a][i]]>=d[b]) {
if(g[a][i][0]>=res.first) {
res.second=max(res.second,max(res.first,g[a][i][1]));
res.first=g[a][i][0];
}
else res.second=max(res.second,g[a][i][0]);
a=f[a][i];
}
return res;
}
int solve() {
int mst=kruskal();
bfs();
int res=0x7fffffffffffffff;
for(int i=1;i<=m;i++) {
if(st[i]) continue;
int mx,lca=LCA(e[i].u,e[i].v);
pair<int,int> t1=calc(e[i].u,lca),t2=calc(e[i].v,lca);
if(t1.first!=t2.first) {
if(max(t1.first,t2.first)==e[i].w) mx=max(max(t1.second,t2.second),min(t1.first,t2.first));
else mx=max(t1.first,t2.first);
}
else {
if(t1.first==e[i].w) mx=max(t1.second,t2.second);
else mx=t1.first;
}
res=min(res,mst-mx+e[i].w);
}
return res;
}
signed main() {
scanf("%lld%lld",&n,&m);
t=(int)log(n)/log(2)+1;
for(int i=1;i<=m;i++) {
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
e[i]=E(u,v,w);
}
printf("%lld\n",solve());
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 543ms, 内存消耗: 33548K, 提交时间: 2022-08-17 11:42:37
#include<bits/stdc++.h>
using namespace std;
#define re int
struct tt{
int x,y,z;
bool friend operator<(tt xx,tt yy){
return xx.z<yy.z;
}
}a[300005],c[300005];
int n,m,fa[100005][17];
int mx[100005][17];
int mn[100005][17],d[100005];
int nt[200005],to[200005];
int h[100005],tot,vl[200005];
inline void add(int x,int y,int z){
nt[++tot]=h[x];h[x]=tot;to[tot]=y;vl[tot]=z;
}
int f[100005],cnt;
inline int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
long long p,q;
inline int smax(int x,int y,int xx,int yy)
{
int aa[4];
aa[0]=x;
aa[1]=y;
aa[2]=xx;
aa[3]=yy;
sort(aa,aa+4);
int u=unique(aa,aa+4)-aa-1;
if(u==1)return -1;
return aa[u-1];
}
void pre(int i,int la)
{
d[i]=d[la]+1;
for(re j=1; (1<<j)<d[i]; j++)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
mx[i][j]=max(mx[i][j-1],mx[fa[i][j-1]][j-1]);
mn[i][j]=smax(mn[i][j-1],mn[fa[i][j-1]][j-1],mx[i][j-1],mx[fa[i][j-1]][j-1]);
}
for(re j=h[i]; j; j=nt[j])
{
if(to[j]==la)
continue;
fa[to[j]][0]=i;
mx[to[j]][0]=vl[j];
mn[to[j]][0]=-1;
pre(to[j],i);
}
}
void lca(int x,int y,int z)
{
int s=-1,ss=-1,u;
if(x==y)return;
if(d[x]<d[y])
swap(x,y);
u=d[x]-d[y];
for(re j=16;j>=0;j--)
if(u&(1<<j))
{
s=max(s,mx[x][j]);
ss=smax(ss,mx[x][j],mn[x][j],s);
x=fa[x][j];
}
if(x==y)
{
if(s<z)
q=min(q,p+z-s);
else
if(ss!=-1)
q=min(q,p+z-ss);
return;
}
for(re j=16;j>=0;j--)
if(fa[x][j]!=fa[y][j])
{
s=max(s,mx[x][j]);ss=smax(ss,mx[x][j],mn[x][j],s);x=fa[x][j];
s=max(s,mx[y][j]);ss=smax(ss,mx[y][j],mn[y][j],s);y=fa[y][j];
}
s=max(s,mx[x][0]);
ss=smax(ss,mx[x][0],mn[x][0],s);
s=max(s,mx[y][0]);
ss=smax(ss,mx[y][0],mn[y][0],s);
if(s<z)q=min(q,p+z-s);
else if(ss!=-1)q=min(q,p+z-ss);
}
signed main(){
scanf("%d%d",&n,&m);
int now=0;
for(re i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
sort(a+1,a+m+1);
for(re i=1;i<=n;i++)
f[i]=i;
for(re i=1;i<=m;i++)
{
if(find(a[i].x)!=find(a[i].y))
{
f[find(a[i].x)]=find(a[i].y);
p+=a[i].z;
now++;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
}
else c[++cnt]=a[i];
}
mx[1][0]=-1;pre(1,0);q=2e18;
for(re i=1;i<=cnt;i++)
lca(c[i].x,c[i].y,c[i].z);
cout<<q<<endl;
return 0;
}
C++(clang++11) 解法, 执行用时: 272ms, 内存消耗: 34892K, 提交时间: 2020-11-04 20:17:46
#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;
}