2013-team4/code/submst
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
严格次小：次小生成树权值和最小生成树不同
非严格次小：次小生成树权值和最小生成树可以相同
方法一：时间复杂度O(N^3)，不推荐使用
1. 求出图G的最小生成树T；
2. 枚举T上的每一条边将其从G中删去，再求一次最小生成树，并记录权值(要求当前权值ω(T')与ω(T)不同)；
3. 步骤2中权值的最小值就是所求的次小生成树.
方法二：时间复杂度O(N^2)或者O(MlogM)，推荐使用，稀疏图需用O(MlogM)的，稠密图需用O(N^2)
1. 求出图G的最小生成树T；
2. 求出T中任意两个结点u和v的路径中最长边和次长边(要求两者不相同，这里的目的是有些题目要求严格次小)；
3. 枚举G中不在T上的每一条边<u,v>，用<u,v>替换u和v的路径中最长边(如果最长边和<u,v>权值相同，那么替换次长边， 目的同上).
}}}
{{{
//N^2版本，严格次小，实现简单
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAXN=1005;
const int inf=1000000000;
vector<int> G[MAXN];
int val[MAXN][MAXN];
int map[MAXN][MAXN];
int pre[MAXN];
int vis[MAXN];
int N;
int prim(int n, int mat[][MAXN], int *pre) {
int Min[MAXN], ret=0;
int i, j, k;
for (i=0; i<n; i++)
Min[i]=inf, vis[i]=false, pre[i]=-1;
for (Min[j=0]=0; j<n; j++) {
for (k=-1, i=0; i<n; i++)
if (!vis[i]&&(k==-1||Min[i]<Min[k]))
k=i;
for (vis[k]=1, ret+=Min[k], i=0; i<n; i++)
if (!vis[i]&&mat[k][i]<Min[i])
Min[i]=mat[pre[i]=k][i];
}
return ret;
}
void dfs(int id, int x, int v) {
vis[x]=true; val[id][x]=v;
for (int i=0; i<G[x].size(); i++) {
int y=G[x][i]; if (vis[y]) continue;
int tmp=v;
if (tmp<map[x][y]) tmp=map[x][y];
dfs(id, y, tmp);
}
}
int solve()
int ret=prim(N, map, pre);
for (int i=0; i<N; i++) G[i].clear();
for (int i=0; i<N; i++)
if (pre[i]!=-1) {
G[i].push_back(pre[i]);
G[pre[i]].push_back(i);
}
int ans=inf;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) vis[j]=false;
dfs(i, i, -1);
for (int j=i+1; j<N; j++)
{
int tmp=ret-value[i][j]+map[i][j];
if (tmp!=ret&&tmp<ans) ans=tmp;
}
return ans;
}
}}}
{{{
//MlogM版本，这里要求严格次小，实现比较复杂，需要求LCA
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN=100000+10;
const int MAXM=300000+10;
const int LOG=22;
struct node {
int u, v, w;
};
node edge[MAXM];
int belong[MAXN];
int head[MAXN], next[MAXM], adj[MAXM], flow[MAXM];
int anc[LOG][MAXN], dp[2][LOG][MAXN];
int dep[MAXN], fa[MAXN];
bool used[MAXM];
int N, M;
LL ret;
bool cmp(const node &a, const node &b) {
return (a.w<b.w);
}
int getf(int x) {
if (x!=belong[x]) belong[x]=getf(belong[x]);
return belong[x];
}
void build() {
int cnt=0, times=0;
for (int i=1; i<=N; i++) head[i]=-1, belong[i]=i;
for (int i=0; i<M; i++) {
int u=edge[i].u, v=edge[i].v, w=edge[i].w;
int fu=getf(u), fv=getf(v); used[i]=false;
if (fu!=fv) {
belong[fu]=fv; ret+=w; times++; used[i]=true;
adj[cnt]=v, flow[cnt]=w, next[cnt]=head[u], head[u]=cnt++;
adj[cnt]=u, flow[cnt]=w, next[cnt]=head[v], head[v]=cnt++;
if (times==N-1) return;
}
}
}
void dfs(int u) {
for (int now=head[u]; now!=-1; now=next[now]) {
int v=adj[now], w=flow[now];
if (dep[v]==-1) {
dep[v]=dep[u]+1;
anc[0][v]=u; dp[0][0][v]=w;
dfs(v);
}
}
}
void get_anc() {
for (int i=1; (1<<i)<=N; i++)
for (int j=1; j<=N; j++)
if (anc[i-1][j]!=-1) {
anc[i][j]=anc[i-1][anc[i-1][j]];
if (anc[i][j]!=-1) dp[0][i][j]=max(dp[0][i-1][j], dp[0][i-1][anc[i-1][j]]);
if (i==1&&dp[0][0][j]!=dp[0][0][anc[0][j]]) dp[1][1][j]=min(dp[0][0][j], dp[0][0][anc[0][j]]);
else if (anc[i][j]!=-1) {
dp[1][i][j]=max(dp[1][i-1][j], dp[1][i-1][anc[i-1][j]]);
if (dp[0][i-1][j]>dp[0][i-1][anc[i-1][j]]) dp[1][i][j]=max(dp[1][i][j], dp[0][i-1][anc[i-1][j]]);
if (dp[0][i-1][j]<dp[0][i-1][anc[i-1][j]]) dp[1][i][j]=max(dp[1][i][j], dp[0][i-1][j]);
}
}
}
inline int lca(int a, int b) {
if (dep[a]<dep[b]) swap(a, b);
int l=(int)(log(N)/log(2))+1;
for (int i=l; i>=0; i--)
if (dep[a]>=dep[b]+(1<<i)) {
a=anc[i][a];
if (a==b) return a;
}
for (int i=l; i>=0; i--)
if (anc[i][a]!=-1&&anc[i][a]!=anc[i][b]) {
a=anc[i][a], b=anc[i][b];
}
return anc[0][a];
}
inline int get_maxlen(int a, int b, int c) {
int res=-1, t=a;
int l=(int)(log(N)/log(2))+1;
for (int i=l; i>=0; i--)
if (dep[a]>=dep[b]+(1<<i)) {
res=max(res, dp[0][i][a]);
a=anc[i][a];
}
if (res!=c) return res;
res=-1; a=t;
for (int i=l; i>=0; i--)
if (dep[a]>=dep[b]+(1<<i)) {
res=max(res, dp[1][i][a]);
a=anc[i][a];
}
return res;
}
void solve() {
build();
for (int i=0; (1<<i)<=N; i++)
for (int j=0; j<=N; j++)
anc[i][j]=dp[0][i][j]=dp[1][i][j]=-1;
for (int i=0; i<=N; i++) dep[i]=-1;
dep[1]=0;
dfs(1);
get_anc();
LL ans=(1ll<<60ll);
for (int i=0; i<M; i++) {
if (used[i]) continue;
int u=edge[i].u, v=edge[i].v, w=edge[i].w;
int root=lca(u, v);
LL tmp=max(get_maxlen(u, root, w), get_maxlen(v, root, w));
if (tmp==-1) continue;
tmp=ret-tmp+w;
if (tmp<ans&&tmp!=ret) ans=tmp;
}
printf("%lld\n", ans);
}
int main() {
scanf("%d%d", &N, &M);
for (int i=0; i<M; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
sort(edge, edge+M, cmp);
solve();
return 0;
}
}}}严格次小：次小生成树权值和最小生成树不同
非严格次小：次小生成树权值和最小生成树可以相同
方法一：时间复杂度O(N^3)，不推荐使用
1. 求出图G的最小生成树T；
2. 枚举T上的每一条边将其从G中删去，再求一次最小生成树，并记录权值(要求当前权值ω(T')与ω(T)不同)；
3. 步骤2中权值的最小值就是所求的次小生成树.
方法二：时间复杂度O(N^2)或者O(MlogM)，推荐使用，稀疏图需用O(MlogM)的，稠密图需用O(N^2)
1. 求出图G的最小生成树T；
2. 求出T中任意两个结点u和v的路径中最长边和次长边(要求两者不相同，这里的目的是有些题目要求严格次小)；
3. 枚举G中不在T上的每一条边<u,v>，用<u,v>替换u和v的路径中最长边(如果最长边和<u,v>权值相同，那么替换次长边， 目的同上).
//N^2版本，严格次小，实现简单
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int MAXN=1005;
const int inf=1000000000;
vector<int> G[MAXN];
int val[MAXN][MAXN];
int map[MAXN][MAXN];
int pre[MAXN];
int vis[MAXN];
int N;
int prim(int n, int mat[][MAXN], int *pre) {
int Min[MAXN], ret=0;
int i, j, k;
for (i=0; i<n; i++)
Min[i]=inf, vis[i]=false, pre[i]=-1;
for (Min[j=0]=0; j<n; j++) {
for (k=-1, i=0; i<n; i++)
if (!vis[i]&&(k==-1||Min[i]<Min[k]))
k=i;
for (vis[k]=1, ret+=Min[k], i=0; i<n; i++)
if (!vis[i]&&mat[k][i]<Min[i])
Min[i]=mat[pre[i]=k][i];
}
return ret;
}
void dfs(int id, int x, int v) {
vis[x]=true; val[id][x]=v;
for (int i=0; i<G[x].size(); i++) {
int y=G[x][i]; if (vis[y]) continue;
int tmp=v;
if (tmp<map[x][y]) tmp=map[x][y];
dfs(id, y, tmp);
}
}
int solve()
int ret=prim(N, map, pre);
for (int i=0; i<N; i++) G[i].clear();
for (int i=0; i<N; i++)
if (pre[i]!=-1) {
G[i].push_back(pre[i]);
G[pre[i]].push_back(i);
}
int ans=inf;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) vis[j]=false;
dfs(i, i, -1);
for (int j=i+1; j<N; j++)
{
int tmp=ret-value[i][j]+map[i][j];
if (tmp!=ret&&tmp<ans) ans=tmp;
}
return ans;
}
//MlogM版本，这里要求严格次小，实现比较复杂，需要求LCA
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN=100000+10;
const int MAXM=300000+10;
const int LOG=22;
struct node {
int u, v, w;
};
node edge[MAXM];
int belong[MAXN];
int head[MAXN], next[MAXM], adj[MAXM], flow[MAXM];
int anc[LOG][MAXN], dp[2][LOG][MAXN];
int dep[MAXN], fa[MAXN];
bool used[MAXM];
int N, M;
LL ret;
bool cmp(const node &a, const node &b) {
return (a.w<b.w);
}
int getf(int x) {
if (x!=belong[x]) belong[x]=getf(belong[x]);
return belong[x];
}
void build() {
int cnt=0, times=0;
for (int i=1; i<=N; i++) head[i]=-1, belong[i]=i;
for (int i=0; i<M; i++) {
int u=edge[i].u, v=edge[i].v, w=edge[i].w;
int fu=getf(u), fv=getf(v); used[i]=false;
if (fu!=fv) {
belong[fu]=fv; ret+=w; times++; used[i]=true;
adj[cnt]=v, flow[cnt]=w, next[cnt]=head[u], head[u]=cnt++;
adj[cnt]=u, flow[cnt]=w, next[cnt]=head[v], head[v]=cnt++;
if (times==N-1) return;
}
}
}
void dfs(int u) {
for (int now=head[u]; now!=-1; now=next[now]) {
int v=adj[now], w=flow[now];
if (dep[v]==-1) {
dep[v]=dep[u]+1;
anc[0][v]=u; dp[0][0][v]=w;
dfs(v);
}
}
}
void get_anc() {
for (int i=1; (1<<i)<=N; i++)
for (int j=1; j<=N; j++)
if (anc[i-1][j]!=-1) {
anc[i][j]=anc[i-1][anc[i-1][j]];
if (anc[i][j]!=-1) dp[0][i][j]=max(dp[0][i-1][j], dp[0][i-1][anc[i-1][j]]);
if (i==1&&dp[0][0][j]!=dp[0][0][anc[0][j]]) dp[1][1][j]=min(dp[0][0][j], dp[0][0][anc[0][j]]);
else if (anc[i][j]!=-1) {
dp[1][i][j]=max(dp[1][i-1][j], dp[1][i-1][anc[i-1][j]]);
if (dp[0][i-1][j]>dp[0][i-1][anc[i-1][j]]) dp[1][i][j]=max(dp[1][i][j], dp[0][i-1][anc[i-1][j]]);
if (dp[0][i-1][j]<dp[0][i-1][anc[i-1][j]]) dp[1][i][j]=max(dp[1][i][j], dp[0][i-1][j]);
}
}
}
inline int lca(int a, int b) {
if (dep[a]<dep[b]) swap(a, b);
int l=(int)(log(N)/log(2))+1;
for (int i=l; i>=0; i--)
if (dep[a]>=dep[b]+(1<<i)) {
a=anc[i][a];
if (a==b) return a;
}
for (int i=l; i>=0; i--)
if (anc[i][a]!=-1&&anc[i][a]!=anc[i][b]) {
a=anc[i][a], b=anc[i][b];
}
return anc[0][a];
}
inline int get_maxlen(int a, int b, int c) {
int res=-1, t=a;
int l=(int)(log(N)/log(2))+1;
for (int i=l; i>=0; i--)
if (dep[a]>=dep[b]+(1<<i)) {
res=max(res, dp[0][i][a]);
a=anc[i][a];
}
if (res!=c) return res;
res=-1; a=t;
for (int i=l; i>=0; i--)
if (dep[a]>=dep[b]+(1<<i)) {
res=max(res, dp[1][i][a]);
a=anc[i][a];
}
return res;
}
void solve() {
build();
for (int i=0; (1<<i)<=N; i++)
for (int j=0; j<=N; j++)
anc[i][j]=dp[0][i][j]=dp[1][i][j]=-1;
for (int i=0; i<=N; i++) dep[i]=-1;
dep[1]=0;
dfs(1);
get_anc();
LL ans=(1ll<<60ll);
for (int i=0; i<M; i++) {
if (used[i]) continue;
int u=edge[i].u, v=edge[i].v, w=edge[i].w;
int root=lca(u, v);
LL tmp=max(get_maxlen(u, root, w), get_maxlen(v, root, w));
if (tmp==-1) continue;
tmp=ret-tmp+w;
if (tmp<ans&&tmp!=ret) ans=tmp;
}
printf("%lld\n", ans);
}
int main() {
scanf("%d%d", &N, &M);
for (int i=0; i<M; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
sort(edge, edge+M, cmp);
solve();
return 0;
}