次小生成树的一种极其神犇的算法

Posted on 2011-07-01 09:10 Mato_No1 阅读(2645) 评论(8)  编辑 收藏 引用 所属分类: 图算法
相关链接

Orz AHdoc!!!!!!!!!!!!!

这种神犇算法的关键在于真正利用了MST是一棵“树”的性质。也就是,它在求出MST后把它转化为有根树,然后,按长度递增顺序对于图中每一条不在MST中的边(i, j),找到树中i、j的最近公共祖先(LCA),记为p=LCA(i, j)。这样,树中i->p->j就是从i到j的路径。然后,依次扫描这条路径上的所有的边,将新边(i, j)的长度与路径上所有边的长度比较,找到长度差最小的(不过由于边(i, j)的长度一定不小于路径上所有边的长度,所以只要找到路径上最长边,则“删去这条最长边,加入边(i, j)”一定是所有加入的边为(i, j)的可行变换中代价最小的),取这个长度差最小的即可。不过最为神犇的一点是,这个算法在遍历完这条路径后,会将路径上所有的点(p点除外)的父结点全部设为p,也就是相当于并查集的路径压缩!这虽然会改变树的形态,但任何两点的LCA都是不会变的,因此不会影响后面的边。

注意上面“按长度递增顺序”是重点,原因是“路径压缩”可能会改变某些点之间的路径,也就是将某些点之间的路径长度减小。但是,很容易发现,被“压缩”的这些边必然是已经访问过的,也就是说这些边必然已经作为了前面的某条边(i, j),i到j路径上的边。对于这条边来说,可行变换中,新加入的边的长度应尽量小,因此,如果按长度递增顺序,则这些边在(i, j)之后肯定不会出现代价更小的可行变换,因此就可以将它们压缩,不会影响最优解。

复杂度分析:先不管求LCA的时间复杂度。设树中结点i的深度为h[i](h[root]=0)。对于树中的任意一个叶结点v,从root到v的路径的总长度(总边数)为h[v],因此,若某次要尝试的边(i, j)的某一端点(设为i)在从root到v的这条路径上,则p=LCA(i, j)一定也在这条路径上。这样,访问从i到p的路径上的总访问次数(也就是从i到p路径上的边数)为(h[i]-h[p])。在访问完成后,需要将从i到p路径上除p外的所有结点的父结点都设为p,也就是从root到v的路径的总长度减少了(h[i]-h[p]-1)。因此,在尝试所有不在MST中的边的过程中,访问从root到v的最初路径上的边的总次数不会超过(h[v]+这些边的总数)(这里h[v]指初始的h[v])。因此可以得到:访问树中所有边的总次数不会超过(最初所有叶结点深度之和+2*M),M为所有不在MST中边的总数!由于“最初所有叶结点深度之和”不会超过Nlog2N,因此总时间复杂度为O(Mlog2M+M+Nlog2N),其中O(Mlog2M)为用Kruskal求MST的时间,如果忽略这部分时间,则总时间复杂度为O(M+Nlog2N)。
其实这个算法的时间复杂度在忽略排序的情况下是线性的,即O(M+N),但本沙茶搞不懂怎么证明这一步。

下面是具体实现时的注意事项:
(1)将MST转化为有根树时,应用BFS,而不要用DFS,否则对于特殊数据可能爆栈;
(2)求LCA时,应用先让深度大的结点向上的方法(AHdoc神犇的方法),具体见下面的代码片段1;或者应用两者同时往上的方法(本沙茶的方法),具体见下面的代码片段2;否则,对于树是一条链,且每次访问都是访问最深的两个结点时,一次求LCA的时间复杂度可能升到O(N)。

【代码片段1】
int lca(int a, int b)
{
    
for (;;)
    {
        
if (a == b) return b;
        
if (h[a] >= h[b]) a = Fa[a]; else b = Fa[b];
    }
}
【代码片段2】
int LCA(int x, int y)
{
    
while (x && y) {
        
if (fl[x] == _s) return x; else fl[x] = _s;
        
if (fl[y] == _s) return y; else fl[y] = _s;
        x 
= pr[x]; y = pr[y];
    }
    
if (x) while (1if (fl[x] == _s) return x; else x = pr[x]; else while (1if (fl[y] == _s) return y; else y = pr[y];
}

【具体题目】Beijing2010 Tree(BZOJ1977)
这题要求严格次小生成树,因此在枚举的时候要注意,不能使可行变换的代价为0。
#include <iostream>
#include 
<stdio.h>
#include 
<algorithm>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
const int MAXN = 100001, MAXM = 300001;
const long long INF = ~0Ull >> 2;
struct edge {
    
int a, b, len;
    friend 
bool operator< (edge e0, edge e1) {return e0.len < e1.len;}
} E[MAXM];
struct edge0 {
    
int a, b, id, pre, next;
} E0[MAXM 
+ MAXM];
int n, m, m0, u[MAXN], pr[MAXN], No[MAXN], s[MAXM], Q[MAXN], fl[MAXN], _s;
long long mst_v = 0, res;
bool inmst[MAXM], vst[MAXN];
void init()
{
    scanf(
"%d%d"&n, &m);
    re(i, m) scanf(
"%d%d%d"&E[i].a, &E[i].b, &E[i].len);
}
int find(int x) {int r = x, r0; while (u[r] > 0) r = u[r]; while (u[x] > 0) {r0 = u[x]; u[x] = r; x = r0;} return r;}
void uni(int s1, int s2) {int tmp = u[s1] + u[s2]; if (u[s1] > u[s2]) {u[s1] = s2; u[s2] = tmp;} else {u[s2] = s1; u[s1] = tmp;}}
void init_d()
{
    re1(i, n) {E0[i].a 
= i; E0[i].pre = E0[i].next = i;}
    
if (n % 2) m0 = n + 1else m0 = n + 2;
}
void add_edge(int a, int b, int id)
{
    E0[m0].a 
= a; E0[m0].b = b; E0[m0].id = id; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
    E0[m0].a 
= b; E0[m0].b = a; E0[m0].id = id; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void prepare()
{
    sort(E, E 
+ m);
    re1(i, n) u[i] 
= -1; init_d();
    
int s1, s2, z = 0;
    re(i, m) {
        s1 
= find(E[i].a); s2 = find(E[i].b);
        
if (s1 != s2) {z++; mst_v += E[i].len; add_edge(E[i].a, E[i].b, i); inmst[i] = 1; uni(s1, s2); if (z == n - 1break;}
    }
}
void bfs()
{
    re1(i, n) vst[i] 
= 0;
    Q[
0= 1; vst[1= 1;
    
int i, j;
    
for (int front=0, rear=0; front<=rear; front++) {
        i 
= Q[front];
        
for (int p=E0[i].next; p != i; p=E0[p].next) {
            j 
= E0[p].b;
            
if (!vst[j]) {
                vst[j] 
= 1; Q[++rear] = j; pr[j] = i; No[j] = E0[p].id;
            }
        }
    }
}
int LCA(int x, int y)
{
    
while (x && y) {
        
if (fl[x] == _s) return x; else fl[x] = _s;
        
if (fl[y] == _s) return y; else fl[y] = _s;
        x 
= pr[x]; y = pr[y];
    }
    
if (x) while (1if (fl[x] == _s) return x; else x = pr[x]; else while (1if (fl[y] == _s) return y; else y = pr[y];
}
void sol0(int a, int b, int l)
{
    
int p = LCA(a, b), p0, No0;
    
while (a != p) {No0 = No[a]; if (!s[No0] && l > E[No0].len) s[No0] = l - E[No0].len; p0 = pr[a]; pr[a] = p; a = p0;}
    
while (b != p) {No0 = No[b]; if (!s[No0] && l > E[No0].len) s[No0] = l - E[No0].len; p0 = pr[b]; pr[b] = p; b = p0;}
}
void solve()
{
    pr[
1= 0; bfs();
    re(i, m) 
if (!inmst[i]) {_s = i + 1; sol0(E[i].a, E[i].b, E[i].len);}
    res 
= INF;
    re(i, m) 
if (inmst[i] && s[i] && s[i] < res) res = s[i];
    res 
+= mst_v;
}
void pri()
{
    cout 
<< res << endl;
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}

Feedback

# re: 次小生成树的一种极其神犇的算法  回复  更多评论   

2011-08-04 13:14 by 南京康辉旅行社
谢谢,正在找呢。。

# re: 次小生成树的一种极其神犇的算法  回复  更多评论   

2011-11-16 18:38 by Seter
看了半天还是觉得神犇您的程序是错误的啊。下面这个数据答案应该是6,您的程序输出7:
4 5
1 4 1
2 3 1
1 2 3
3 4 3
3 4 4
问题在于,路径压缩的正确性是建立在选择路径上的最大边的条件上的,而您的严格次小生成树忽略了权值相等的边,使得可行变换的单调性无法维持。
路径压缩时修改边权可能可以解决这一问题。

# re: 次小生成树的一种极其神犇的算法[未登录]  回复  更多评论   

2011-11-24 17:04 by xiaodao
@Seter
是有重边的缘故么?

# re: 次小生成树的一种极其神犇的算法  回复  更多评论   

2011-11-28 18:50 by Seter
@xiaodao
重边是最简单的一种可以导致这个算法错误的情况……
这个证明是建立在“不严格”的基础下的……
如果要应用于“严格”,那么必须修改算法并且重新证明……

# re: 次小生成树的一种极其神犇的算法  回复  更多评论   

2011-12-04 12:13 by Mato_No1
@xiaodao
找到问题了,
问题并不在于重边,而是在于出现权值相等的边的时候,由于严格次小生成树的定义,这种变换(就是用权值相等的边来替换)是不可行的,然而紧接着又把它们压缩掉了,这样,接下来这条路径上出现权值不相等的边的时候由于压缩,就把某些可行变换给搞丢了,
比如,
P-3-O-1-Z-1-X
\
1
\
O-3-O-3-O-1-W-1-Y
(P表示LCA,O、Z、W表示中间结点,两个结点间的数字表示边权)
然后,先是扫描到一条边(X, Y)权值为3,发现只能和那些权值为1的边之间形成可行变换,最小代价为2,于是就压缩了,但是在此之后又出现了一条边(Z, W)权值为4,此时它们之间的长度为3的那些边就找不到了,导致最优解(代价为1)丢失。

一种解决方法是遇到这种情况就彻底不压缩,或者是只压缩与P最近的那些权值不相等的边,但是在某些极端情况下复杂度可能退化到O(NM)……

神犇们有更好的解决方法么囧?急求

# re: 次小生成树的一种极其神犇的算法  回复  更多评论   

2012-02-02 19:11 by Seter
@Mato_No1
我的想法是这样的:1.每次不仅找i->p->j上的最长边,还要找严格次长边。2.路径压缩时,新边i->p的长度设为i->p这条路径上的最长的长度。
我稍微证了一下,这个应该没什么问题了。

# re: 次小生成树的一种极其神犇的算法  回复  更多评论   

2012-02-03 09:08 by Seter
LS在瞎说,请神犇们无视!
难道真的无解了么……

# re: 次小生成树的一种极其神犇的算法  回复  更多评论   

2012-09-03 18:54 by void_rank
5 6
1 2 1
1 3 8
2 4 8
4 5 1
3 4 10
4 3 3

好像神犇的这个数据跪了,是不是我的测试方法不对,求证实?

然后我看完上面的回复好像发现了lz的问题,代码没改过来么。。。。。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理