题解 P4180 【【模板】严格次小生成树[BJWC2010]】
Jμdge
2018-04-19 09:38:57
然鹅刚刚有同学指出我的代码有bug，样例都过不了（然鹅还是AC了我也是...）
于是看了看，确实某个地方有点草率，于是把自己修改正确了的代码放到第一个，错的第二个，还有另一个放在第三个。。。
（楼下一堆大佬有没有出错的我就不知道了，但是貌似出错的程序也是能过的）。于是来发篇程序里头注解比较多的题解 。如果是那种思路的话还是看楼下大佬的吧，我的题解一般来讲是帮助童鞋们理解程序构造云云的...（QAQ 不喜勿喷）
但是这次还是好好分析一下吧~~（哪怕是按着代码思路来一遍）~~。
首先的首先，这个blog大家可以先看看（对于次小生成树的分析比我详细，看完这篇blog再看本蒟蒻的题解效果更佳。QAQ```_(:з」∠)_```）：
[某大佬的blog](https://blog.csdn.net/zhongshijunacm/article/details/12992571)
------------
```
首先的话，想必做到这题的童鞋都知道最小生成树mst怎么写了吧。
那么其实次小生成树也是可以分为两种的（严格和非严格），怎么说呢...
as we all know，mst是指一个图中所有包含全部顶点的树中边权和最小的树，
那么我们所说的严格次小生成树就是边权之和严格大于（也就是不能等于），但是又是满足该条件的生成树里边权之、和最小的树。
比如说某图的最小生成树的边权和为88，还有其他的几个生成树的边权和分别为88、88、90、100、103、111，
那么边权和为90的生成树就是该图的严格次小生成树，
而另外另一棵边权和为88的生成树就是该图的非严格次小生成树（此时这棵树的边权和 与 mst的边权和相等了呀）。
那么易知当一个图的mst唯一时，该图的严格次小生成树与非严格次小生成树就区别不大了。
那么怎么求一个图的次小生成树捏？以下是步骤：
1.首先读边什么的就不说了，那么第一步就是用kruskal跑一遍mst，并且把用到的边打上标记，然后还要记录下mst的边权和；
2.其次再把这些打上标记的边存到该边指向的两个顶点的后面（两个顶点都要存），以便接下来深搜建树用。
3.深搜建树，并维护好当前节点的一系列信息（比如说当前点祖先的信息啦、从当前点到某个祖先的路径中的最大边权和次大边权啦之类的）
4.再然后就是枚举无用边（最小树中没有用到的边），然后倍增找当前枚举到的边所指向的两个端点的lca并且求出路径中最大边权和次大边权，
当前枚举到的边减去找出的最大（或许是次大）的边权就是该边的贡献，然后最小贡献记录进ans里。
5.printf 边权和res + （非零的）最小贡献ans ，完毕
```
------------
```
//by Judge
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
typedef long long ll;
using namespace std;
const int M=1e5+100;
ll n,m,res,ans=0x3f3f3f3f,mx;
int f[M],fa[25][M],dep[M];
ll d[2][25][M];
bool used[3*M],vis[M];
vector<int> a[M];
struct Edge{
int from, to;
ll val;
bool operator < (const Edge y){
return val < y.val;
}
}e[3*M];
int F(int x){
if(f[x]==x) return x;
return f[x]=F(f[x]);
}
void kruskal(){ //kruskal 算最大生成树（已保证任意两点之间最小限重最优）
sort(e,e+m); int lef=n-1;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=0;i<m && lef;++i){
int x=F(e[i].from),y=F(e[i].to);
if(x!=y){
f[x]=y; res+=e[i].val;
used[i]=1; --lef;
mx=max(mx , e[i].val);
}
}
}
void dfs(int x){ //深搜建树（可能不止一棵，因为数据未保证是连通图）
vis[x]=true;
for(int i=1;i<=23;++i){
fa[i][x]=fa[i-1][fa[i-1][x]];
ll t1=d[0][i-1][x], t2=d[0][i-1][fa[i-1][x]];
d[0][i][x]=max(t1 , t2);
d[1][i][x]=max(d[1][i-1][x] , d[1][i-1][fa[i-1][x]]);
if(t1!=t2) d[1][i][x]=max(d[1][i][x] , min(t1 , t2));
}
for(int i=0;i<a[x].size();++i){
int t=e[a[x][i]].to+e[a[x][i]].from-x;
if(vis[t]) continue; //vis为1表示是父节点
dep[t]=dep[x]+1; fa[0][t]=x;
d[0][0][t]=e[a[x][i]].val; dfs(t);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])
swap(u,v);
if(dep[u]!=dep[v]){ //将深度做相等
for(int i=23,h=dep[u]-dep[v];i>=0;--i)
if(h&(1<<i)) u=fa[i][u];
}
if(u==v) return u; //如果已经在一个节点上就直接返回
for(int i=23;i>=0;--i) if(fa[i][u]!=fa[i][v])
u=fa[i][u] , v=fa[i][v];
return fa[0][u];
}
ll get(int u,int v,int c){
int fht=lca(u,v);
ll m1=0,m2=0;
for(int i=23,h1=dep[u]-dep[fht],h2=dep[v]-dep[fht];i>=0;--i){
if(h1&(1<<i)){
if(d[0][i][u]>m1) m2=m1,m1=d[0][i][u];
else if(d[0][i][u]>m2) m2=d[0][i][u];
else m2=max(m2 , d[1][i][u]);
} if(h2&(1<<i)){
if(d[0][i][v]>m1) m2=m1,m1=d[0][i][v];
else if(d[0][i][v]>m2) m2=d[0][i][v];
else m2=max(m2 , d[1][i][v]);
}
} if(m1==c) return c-m2;
else return c-m1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i){
int u,v; ll w;
scanf("%d%d%lld",&u,&v,&w);
e[i].from=u;
e[i].to=v;
e[i].val=w;
} kruskal();
for(int i=0;i<m;++i) if(used[i]){
a[e[i].from].push_back(i);
a[e[i].to].push_back(i);
} dep[1]=1; dfs(1);
for(int i=0;i<m;++i) if(!used[i]){
if(e[i].val-mx>ans) break;
ll t=get(e[i].from , e[i].to , e[i].val);
ans=min(ans , t);
} return printf("%lld\n",res+ans),0;
}
```
原来错的我也不删了，同学们可以开个文本比对看看哪里不一样
```cpp
//by Judge
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
typedef long long ll;
using namespace std;
const int M=1e5+100;
ll n,m,res,ans=0x3f3f3f3f,mx;
int f[M],fa[25][M],dep[M];
ll d[2][25][M];
bool used[3*M],vis[M];
vector<int> a[M];
struct Edge{
int from, to;
ll val;
bool operator < (const Edge y){
return val < y.val;
}
}e[3*M];
int F(int x){ //并查集标准模板
if(f[x]==x) return x;
return f[x]=F(f[x]);
}
void kruskal(){ //kruskal 算mst， 基本就是模板
sort(e,e+m); int lef=n-1;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=0;i<m && lef;++i){
int x=F(e[i].from),y=F(e[i].to);
if(x!=y){
f[x]=y; res+=e[i].val;
used[i]=1; --lef;
mx=max(mx , e[i].val); //这里处理出的mx作剪枝用
}
}
}
void dfs(int x){ //深搜建树，从1开始
vis[x]=true;
for(int i=1;i<=23;++i){
fa[i][x]=fa[i-1][fa[i-1][x]];
ll t1=d[0][i-1][x], t2=d[0][i-1][fa[i-1][x]];
d[0][i][x]=max(t1 , t2);
d[1][i][x]=max(d[1][i-1][x] , d[1][i-1][fa[i-1][x]]);
if(t1!=t2) d[1][i][x]=max(d[1][i][x] , min(t1 , t2));
}
for(int i=0;i<a[x].size();++i){
int t=e[a[x][i]].to+e[a[x][i]].from-x;
if(vis[t]) continue; //vis为1表示是父节点
dep[t]=dep[x]+1; fa[0][t]=x;
d[0][0][t]=e[a[x][i]].val; dfs(t);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])
swap(u,v);
if(dep[u]!=dep[v]){ //将深度做相等
for(int i=23,h=dep[u]-dep[v];i>=0;--i)
if(h&(1<<i)) u=fa[i][u];
}
if(u==v) return u; //如果已经在一个节点上就直接返回
for(int i=23;i>=0;--i) if(fa[i][u]!=fa[i][v])
u=fa[i][u] , v=fa[i][v];
return fa[0][u];
}
ll get(int u,int v,int c){
int fht=lca(u,v);
ll m1=-1,m2=-1; //m1是最大边权,m2是次大边权
// 倍增求最大边权和次大边权
for(int i=23,h1=dep[u]-dep[fht],h2=dep[v]-dep[fht];i>=0;--i){
if(h1&(1<<i)){
if(d[0][i][u]>m1) m2=m1,m1=d[0][i][u];
m2=max(m2 , d[1][i][u]);
}
if(h2&(1<<i)){
if(d[0][i][v]>m1) m2=m1,m1=d[0][i][v];
m2=max(m2 , d[1][i][v]);
}
}
if(m1!=c) return c-m1;
//最大边权和当前关键边的权值相等返回次大边权的贡献(因为本题的次小生成树是严格的)
if(m2!=-1) return c-m2; //不然直接返回最大边权的贡献（这里是hack的关键哦，因为m1==c且m2==-1时代表该环只有一种权值）
//另外这个分函数里也可以把-1都改成0，别问我为什么，数据水你问数据去。
return 0; //不然嘛...返回个0(当然很明显,无解的情况也能由此判断，加些语句就ok了)
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i){ //读边
int u,v; ll w;
scanf("%d%d%lld",&u,&v,&w);
e[i]=(Edge){u , v , w};
}
kruskal(); //跑一边最小生成树
for(int i=0;i<m;++i) if(used[i]){ //记录下mst用到的边，分别加到两个点后面
a[e[i].from].push_back(i);
a[e[i].to].push_back(i);
}
dep[1]=1; dfs(1); //深搜根节点(1)
for(int i=0;i<m;++i) if(!used[i]){ //然后枚举无用边作为关键边
if(e[i].val-mx>ans) break; //剪枝，贡献不可能再小的时候直接break
ll t=get(e[i].from , e[i].to , e[i].val); //求出贡献
if(t) ans=min(ans , t); //最小贡献存进ans
}
printf("%lld\n",res+ans); //输出最小生成树的边权和加上(非零的)最小贡献就是次小生成树
return 0;
}
```
------------
然后发一波老师被我hack掉的代码~ （滑稽）
------------
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=100010,maxm=300010,maxk=22;
using namespace std;
typedef long long ll;
int n,m,pre[maxm],now[maxn],son[maxm],val[maxm],delta=(int)1e9+7,tot;ll ans;
int fa[maxn][maxk],fim[maxn][maxk],sem[maxn][maxk],dep[maxn],f[maxn];bool in[maxm];
struct Edge{int x,y,v;}E[maxm];
bool operator <(Edge a,Edge b){return a.v<b.v;}
void add(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}
int getfa(int x){return f[x]==x?x:f[x]=getfa(f[x]);}
void dfs(int x){
for (int i=1;i<=18;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
int t1=fim[x][i-1],t2=fim[fa[x][i-1]][i-1];
fim[x][i]=max(t1,t2);
sem[x][i]=max(sem[x][i-1],sem[fa[x][i-1]][i-1]);
if (t1!=t2) sem[x][i]=max(sem[x][i],min(t1,t2));
}
for (int y=now[x];y;y=pre[y]) if (son[y]!=fa[x][0]){
dep[son[y]]=dep[x]+1,fa[son[y]][0]=x;
fim[son[y]][0]=val[y],dfs(son[y]);
}
}
void kruskal(){
sort(E+1,E+1+m);int cnt=0;
for (int i=1;i<=n;i++) f[i]=i;
for (int i=1;i<=m&&cnt<n-1;i++){
int x=E[i].x,y=E[i].y,v=E[i].v;
if (getfa(x)==getfa(y)) continue;
cnt++,f[getfa(x)]=getfa(y),ans+=v,in[i]=1;
add(x,y,v),add(y,x,v);
}
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for (int h=dep[x]-dep[y],i=18;i>=0&&h;i--) if (h&(1<<i)) x=fa[x][i];
if (x==y) return x;
for (int i=18;i>=0;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void query(int x,int u,int v){
int max1=0,max2=0;
for (int i=18,h=dep[x]-dep[u];i>=0;i--) if (h&(1<<i)){
if (fim[x][i]>max1) max2=max1,max1=fim[x][i];
max2=max(max2,sem[x][i]),h-=(1<<i);
}
if (v==max1) delta=min(delta,v-max2);
else delta=min(delta,v-max1);
}
void solve(int id){
int x=E[id].x,y=E[id].y,v=E[id].v,u=lca(x,y);
query(x,u,v),query(y,u,v);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1,x,y,z;i<=m;i++)
scanf("%d%d%d",&x,&y,&z),E[i]=(Edge){x,y,z};
kruskal(),dfs(1);
for (int i=1;i<=m;i++) if (!in[i]) solve(i);
printf("%lld\n",ans+delta);
return 0;
}
```
------------
这就hack了？如果你不信的话这里有组数据：
```
input：复制（手动）
5 6
1 2 3
1 3 3
2 3 3
3 4 3
3 5 3
4 5 8
the answer： 粘贴（滑稽）
17
wrong answer：
15
```