[BeiJing2010组队]次小生成树 Tree 【大规模的严格次小生成树】【犀利版Tarjan】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1977

【算法分析】

这道题本应该倍增的方法也应该可以AC得，但是时间卡得太紧。。。无奈TLE。

先说这种AC的算法吧。

1、先用kruskal进行MST。

2、如果尝试用一条边去搞进去的话，那么就要求对应两点中那条树链中的最大权边或者次大权边，才能知道假如包含这条边的严格次小生成树是多大。

AC的算法是这么实现的。

这种方法来源于：http://hi.baidu.com/wjbzbmr/blog/item/c3c8ff0455e3c87003088121.html

在求LCA的Tarjan算法中，我们利用并差集和DFS序实现，实际上在用并差集维护的时候，可以同时维护出到当前子树根的树链上的最大/次大权边。其实如果有比较深刻的体会的话，不难实现。

第二种算法(TLE)

在实现第二步的时候，使用倍增思想。

Fp[i][j]表示i这个结点，向上2^j个父亲，是谁。

FL[i][j][0..1]表示i这个结点，到向上2^j个父亲这条树链上，最大值和次大值分别是多少。

我们定义根的结点为其本身，那么就可以类似RMQ地求出这两个数组。

求他的复杂度为O(n lg n)。

然后每次询问(x,y)的时候，我们只要知道Lca(x,y)，然后利用2^k步长的类似爬山的走法。就可以达到每次询问，回答的复杂度是O(n lg n)

第三种算法。

用树链剖分去解。。。但是第二种常数比较小的都A不了。。。这个就不用看了= =

【其它】

泪流满面，这么多天了，终于AC。

另外我的C++代码是算法二的，提交显示TLE，但利用批处理经过随机大量大小数据，答案与AC程序是一致的。。。

然后我之所以用Pascal，是因为C++可能要爆栈。。。所以要手写栈。

而Pascal能用编译开关调栈~= =

【CODE】【Pascal】【算法一】【AC】

{$M 10000000}
{$inline on}
const
inf=’input.txt’;
ouf=’output.txt’;
max_num=1000000000;

type
gtp=record
        y,w,zz,next:longint;
      end;
arr=array [0..1] of longint;
node=record
         x,y,w:longint;
         res:arr;
         used:boolean;
       end;

var
n,m,e,qe,lca_e:longint;
mstw:int64;
g:array [0..205555] of gtp;
qg,lca_g:array [0..605555] of gtp;
data:array [1..300000] of node;
Q,v,f,ls,qls,lca_ls:array [1..100000] of longint;
d:array [1..100000] of arr;

procedure init;
var
i:longint;
begin
e:=1; qe:=1;
read(n,m);
for i:=1 to m do
    with data[i] do
      begin
        read(x,y,w);
        used:=false;
        res[0]:=-max_num;
        res[1]:=-max_num;
      end;
for i:=1 to n do
    begin
      d[i,0]:=-max_num;
      d[i,1]:=-max_num;
    end;
end;

procedure sort(l,r:longint);
var
i,j,mid:longint;
tmp:node;
begin
if l>=r then exit;
mid:=data[(l+r) div 2].w;
i:=l; j:=r;
repeat
    while data[i].w    while data[j].w>mid do dec(j);
    if i<=j then
      begin
        tmp:=data[i]; data[i]:=data[j]; data[j]:=tmp;
        inc(i); dec(j);
      end;
until i>j;
sort(l,j);
sort(i,r);
end;

procedure addedge(x,y,w:longint);
begin
inc(e);
g[e].y:=y; g[e].next:=ls[x]; ls[x]:=e; g[e].w:=w;
end;

function gf(k:longint):longint;
begin
if f[k]=k then exit(k);
f[k]:=gf(f[k]);
exit(f[k]);
end;

procedure MST;
var
i,times:longint;
begin
times:=0;
for i:=1 to n do f[i]:=i;
for i:=1 to m do
    with data[i] do
      if gf(x)<>gf(y) then
        begin
          f[f[x]]:=f[y];
          used:=true;
          addedge(x,y,w);
          addedge(y,x,w);
          inc(MSTw,w);
          inc(times);
        end;
i:=4;
end;

procedure addq(x,y:longint);
begin
inc(qe);
qg[qe].y:=y; qg[qe].next:=qls[x]; qls[x]:=qe;
end;

procedure build;
var
i,j:longint;
begin
for i:=1 to m do
    with data[i] do
      begin
        addq(x,y);
        qg[qe].zz:=i;
        addq(y,x);
        qg[qe].zz:=i;
      end;
end;

procedure Add_Lca_Link(p,y:longint); inline;
begin
inc(lca_e);
lca_g[lca_e].y:=y;
lca_g[lca_e].next:=lca_ls[p];
lca_ls[p]:=lca_e;
end;

procedure push(var res:arr;w:longint); inline;
begin
if w=res[0] then exit;
if w>res[0] then
    begin
      res[1]:=res[0];
      res[0]:=w;
      exit;
    end;
if w>res[1] then res[1]:=w;
end;

procedure union(k:longint);
var
i,root,tmp,Qt:longint;
res:arr;
begin
i:=k;
Qt:=0;
res[0]:=-max_num;
res[1]:=-max_num;
while f[i]<>i do
    begin
      inc(Qt);
      Q[Qt]:=i;
      i:=f[i];
    end;
inc(Qt);
Q[Qt]:=i;
for i:=Qt downto 1 do
    begin
      push(d[Q[i]],res[0]);
      push(d[Q[i]],res[1]);
      push(res,d[Q[i]][0]);
      push(res,d[Q[i]][1]);
      f[Q[i]]:=Q[Qt];
    end;
end;

procedure dfs(p,fa,w:longint);
var
t:longint;
begin
t:=ls[p];
while t>0 do
    begin
      if g[t].y<>fa then
        dfs(g[t].y,p,g[t].w);
      t:=g[t].next;
    end;

t:=qls[p];
while t>0 do
    with qg[t] do
      begin
        if v[y]=1 then
          begin
            union(y);
            Add_Lca_Link(f[y],zz);
          end;
        t:=next;
      end;

t:=lca_ls[p];
while t>0 do
    with lca_g[t] do
      begin
        union(data[y].x); union(data[y].y);
        push(data[y].res,d[data[y].x,0]);
        push(data[y].res,d[data[y].x,1]);
        push(data[y].res,d[data[y].y,0]);
        push(data[y].res,d[data[y].y,1]);
        t:=next;
      end;

f[p]:=fa;
push(d[p],w);
v[p]:=1;
end;

procedure Tarjan;
var
i,j:longint;
begin
for i:=1 to n do f[i]:=i;
dfs(1,1,-max_num);
end;

function min(x,y:int64):int64;
begin
if x         else min:=y;
end;

procedure solve;
var
i:longint;
ans:int64;
begin
ans:=int64(maxlongint)*int64(maxlongint);
for i:=1 to m do
    if not data[i].used then
      begin
        if data[i].res[0]=-max_num then data[i].res[0]:=0;
        if data[i].res[0]<>data[i].w then
          ans:=min(ans,MSTw-data[i].res[0]+data[i].w)
        else if data[i].res[1]<>-max_num then
          ans:=min(ans,MSTw-data[i].res[1]+data[i].w);
      end;
writeln(ans);
end;

begin
init;
sort(1,m);
MST;
build;
Tarjan;
solve;
end.

【CODE】【C++】【算法二（倍增）】【TLE】

#include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int N=100005;
const int E=300005;
const int INF=1000000000;
const int LgN=20;
typedef __int64 lld;
struct edge{int x,y,w,next;}g[N*2];
int n,m,e,Qt;
lld MSTw;
int ls[N],F[N],FL[N][LgN][2],Fp[N][LgN],List[N],depth[N],fa[N],QL[N*2],R[N],LCA[N*2][LgN];
int Lg[N];
struct data{int x,y,w;bool used;}L[E];
inline int cmp(const void *A,const void *B){return ((data*)A)->w-((data*)B)->w;}

void Read(int &x){
     char ch=getchar();
    
}

inline void init(){
     scanf("%d%d",&n,&m);
     for (int i=1;i<=m;i++){
       scanf("%d%d%d",&L[i].x,&L[i].y,&L[i].w);
       L[i].used=false;
     }
}

inline void addedge(int x,int y,int w){
     g[++e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
     g[++e].x=y; g[e].y=x; g[e].w=w; g[e].next=ls[y]; ls[y]=e;
}

inline int GF(int v){
    int res,i,tmp;
    for (i=v;F[i]!=i;i=F[i]);
    res=i;
    for (i=v;F[i]!=i;tmp=F[i],F[i]=res,i=tmp);
    return res;
}

inline void MST(){
     e=1; memset(ls,0,sizeof(ls));
     MSTw=0;
     int tt=n;
     for (int i=1;i<=n;i++) F[i]=i;
     for (int i=1;i<=m;i++)
       if (GF(L[i].x)!=GF(L[i].y)){
         L[i].used=true;
         addedge(L[i].x,L[i].y,L[i].w);
         F[F[L[i].x]]=F[L[i].y];
         MSTw+=L[i].w;
         tt–;
         if (tt==1) break;
       }
     return;
}

inline void bfs(){
     fa[1]=0;
     int head=0,tail=1,x,y;
     List[1]=1; depth[1]=1;
     while (head!=tail){
           head++;
           for (int t=ls[List[head]];t;t=g[t].next){
               x=g[t].x; y=g[t].y;
               if (t!=(fa[x]^1)){
                 List[++tail]=y;
                 fa[y]=t;
                 depth[y]=depth[x]+1;
               }
           }
     }
}

int stack,t[N],v[N];
inline void Hand_Write_Dfs(){
     int i,y;
     for (i=1;i<=n;i++) t[i]=ls[i];
     List[1]=stack=v[1]=R[1]=Qt=QL[1]=1;
     while (stack){
          if (!t[List[stack]])
            stack–;
          else{
            int &tt=t[List[stack]];
            if (tt!=ls[List[stack]]) QL[++Qt]=List[stack];
            y=g[tt].y;
            tt=g[tt].next;
            if (!v[y]){
              List[++stack]=y;
              v[y]=1;
              QL[++Qt]=y;
              R[y]=Qt;
            }
          }
     }
}

inline void Make_LCA(){
     int i,k,s;
     for (i=1;i<=Qt;i++) LCA[i][0]=QL[i];
     for (k=1;1<       s=1<<(k-1);
       for (i=1;i+(1<         if (depth[LCA[i][k-1]]           LCA[i][k]=LCA[i][k-1];
         else
           LCA[i][k]=LCA[i+s][k-1];
     }
}

inline void Push(int *F1,int *F2){
       if (F2[0]>F1[0]) {F1[1]=F1[0]; F1[0]=F2[0];}else
       if (F2[0]>F1[1] && F2[0]!=F1[0]) F1[1]=F2[0];
       if (F2[1]>F1[0]) {F1[1]=F1[0]; F1[0]=F2[1];}else
       if (F2[1]>F1[1] && F2[1]!=F1[0]) F1[1]=F2[1];
}

inline void Make_Fa(){
     g[0].x=1; g[0].y=1; g[0].w=0;
     g[1].x=1; g[1].y=1; g[0].w=0;
     int i,k,s;
     for (i=1;i<=n;i++){
         FL[i][0][0]=g[fa[i]].w;
         FL[i][0][1]=-INF;
         Fp[i][0]=g[fa[i]].x;
     }
     for (k=1;1<       for (i=1;i<=n;i++){
           Fp[i][k]=Fp[Fp[i][k-1]][k-1];
           FL[i][k][0]=-INF;
           FL[i][k][1]=-INF;
           Push(FL[i][k],FL[i][k-1]);
           Push(FL[i][k],FL[Fp[i][k-1]][k-1]);
       }
}

inline void Make_Log(){
     Lg[1]=0;
     for (int i=2;i<=Qt;i++)
       if (1 << (Lg[i-1]+1)==i)
         Lg[i]=Lg[i-1]+1;
       else
         Lg[i]=Lg[i-1];
}

inline int Get_Lca(int l,int r){
    if (l>r){l^=r;r^=l;l^=r;}
    int k=Lg[r-l+1];
    if (depth[LCA[l][k]]      return LCA[l][k];
    else
      return LCA[r-(1<}

int res[2];
inline void Get_Max(int x,int y){
     int i,k=Lg[n];
     i=y;
     while (i!=x){
           while (depth[Fp[i][k]]           Push(res,FL[i][k]);
           i=Fp[i][k];
     }
}

inline void solve(){
     int i,Lca;
     lld ans=(lld)(1) << 60;
     for (i=1;i<=m;i++)
       if (!L[i].used){
         Lca=Get_Lca(R[L[i].x],R[L[i].y]);
         res[0]=-INF;
         res[1]=-INF;
         Get_Max(Lca,L[i].x);
         Get_Max(Lca,L[i].y);
         if (res[0]!=L[i].w)
           ans=min(ans,MSTw-res[0]+L[i].w);
         else if (res[1]!=-INF)
           ans=min(ans,MSTw-res[1]+L[i].w);
       }
     printf("%I64dn",ans);
}

int main(){
    init();
    qsort(L+1,m,sizeof(data),cmp);
    MST();
    bfs();
    Hand_Write_Dfs();
    Make_LCA();
    Make_Fa();
    Make_Log();
    solve();
    return 0;
}