题解 P4180 【【模板】严格次小生成树[BJWC2010]】

· · 题解

事实证明,本题的数据仍然不够强.bzoj上面原本的数据也是这样的.
一边不断咒骂自己实在太不要脸,一边还是写了题解.

首先我们还是来想想那个非严格次小生成树.
枚举每一条非树边,把路径上的最大值减掉再加上该边的权值.求出一个最小值就是答案.
我知道标算要维护次大边,这样确实不好写.
然后我不禁想:严格次小生成树的总权值大于最小生成树,所以我在枚举刚才的答案时对严格大于最小生成树的结果取最小值,这样进行贪心.
我不知道大家是否看懂了上面这句话.
那么显然上面这个奇怪的算法肯定是错的,但是稍微想一下我发现非常不好hack.
要想hack掉这个,你需要产生一组次大边产生次小生成树的数据.
由于随机数据出现这样的情况的概率非常低(目前的情况是1个小时没有拍出一组hack成功的数据.),所以最后我还是抱着试试看的心情交了一遍.WA90.
我看那个唯一的错误点运行的时间,2ms.
那时候我开始窃喜.然后我开始特判边数非常小的数据,用暴力跑出所有生成树.
然后非常普通的A了.
额.不过我旁边的大佬用两个小时搞出了一组能够hack我的数据.
代码就放在下面了,大家笑一下就好.

#include<bits/stdc++.h>
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int yuzu=4e5;
const ll inf=1e16;
typedef int fuko[yuzu|10];
int n=read(),m=read(),cnt,ecnt;
fuko vis,head;
struct node{
int u,v,cost;
void rd(){u=read(),v=read(),cost=read();}
bool operator <(const node &b) const{
  return cost<b.cost;
  }
}b[yuzu|10];

struct dsu{
fuko fa;
void init(int n){for (int i=1;i<=n;++i) fa[i]=i;}
int find(int x){return fa[x]^x?fa[x]=find(fa[x]):x;}
int mg(int u,int v){
  int fu=find(u),fv=find(v);
  return fu^fv?fa[fu]=fv,1:0;
  }
}my_;

struct edge{int fr,to,cost,next;}e[yuzu<<1|13];
void add(int u,int v,int c){e[++ecnt]=edge{u,v,c,head[u]},head[u]=ecnt;}

ll mst;
ll getmst(){
for (int i=1;i<=m;++i){
  int u=b[i].u,v=b[i].v,c=b[i].cost;
  if (my_.mg(u,v)){
    vis[i]=1,mst+=c;
    add(u,v,c),add(v,u,c);
    }
  }return mst;
}

/*求非严格最小生成树用的是树链剖分,可以求出树上两点间的最大值.
  树剖之类的全是模板,相信不用我多做解释.*/
namespace tree_chain_splitting{
fuko fa,son,sz,dep,ord,dfn,top,a;

void dfs1(int u,int f){
  sz[u]=1,dep[u]=dep[fa[u]=f]+1;
  for (int i=head[u];i;i=e[i].next){
    int v=e[i].to;
    if (v^f){
      dfs1(v,u),sz[u]+=sz[v];
      if (sz[v]>sz[son[u]]) son[u]=v;
      }
    }
  }
void dfs2(int u,int _top){
  top[u]=_top,dfn[ord[++cnt]=u]=cnt;
  if (son[u]) dfs2(son[u],_top);
  for (int i=head[u];i;i=e[i].next){
    int v=e[i].to;
    if (v^fa[u]&&(v^son[u])) dfs2(v,v);
    }
  }

typedef ll karen[yuzu<<2|13];
struct segtree{
#define le rt<<1
#define ri le|1
#define ls le,l,mid
#define rs ri,mid+1,r
karen da;
void build(int rt=1,int l=1,int r=n){
  if (l==r) da[rt]=a[l];
  else{
    int mid=l+r>>1;
    build(ls),build(rs);
    da[rt]=max(da[le],da[ri]);
    }
  } 
ll query(int ql,int qr,int rt=1,int l=1,int r=n){
  if (ql>r||qr<l) return -inf;
  if (ql<=l&&qr>=r) return da[rt];
  int mid=l+r>>1;
  return max(query(ql,qr,ls),query(ql,qr,rs));
  }
}llx;

void preedge(){
  for (int i=1;i<=m;++i) if (vis[i]){
    int u=b[i].u,v=b[i].v;
    if (dep[u]>dep[v]) swap(u,v);
    a[dfn[v]]=b[i].cost;
    }
  }

ll query(int u,int v){
  ll ans=-inf;
  for (;top[u]^top[v];u=fa[top[u]]){
    if (dep[top[u]]<dep[top[v]]) swap(u,v);
    ans=max(ans,llx.query(dfn[top[u]],dfn[u]));
    }
  if (dep[u]>dep[v]) swap(u,v);
  return max(ans,llx.query(dfn[u]+1,dfn[v]));
  }

int main(){
  int i;
  dfs1(1,0),dfs2(1,1);
  preedge(),llx.build();
  ll zxy=inf;
  for (i=1;i<=m;++i) if (!vis[i]){
    int u=b[i].u,v=b[i].v;
    ll tmp=mst-query(u,v)+b[i].cost;
    if (tmp>mst) zxy=min(zxy,tmp); 
    }write(zxy);
  }
}

namespace m_less_than_11{//暴力枚举组合数不用我解释吧.
ll llx=inf;
fuko a;
/*m:k k:n-1 n:m*/
void dfs(int k,int p){
if (k>=n){
  ll tmp=0;
  for (int i=1;i<n;++i) tmp+=b[a[i]].cost;
  if (tmp>mst) llx=min(llx,tmp);
  return;
  }
for (int i=p+1;i<=m+k-n+1;++i){
  a[k]=i,dfs(k+1,i);
  }
}

int main(){
  dfs(1,0);
  write(llx);
  }
}

int main(){
int i,j;
my_.init(n);
for (i=1;i<=m;++i) b[i].rd();
sort(b+1,b+m+1),getmst();
if (m<=15) return m_less_than_11::main(),0;
tree_chain_splitting::main();
}