【题目链接】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;
}
