最小生成树
无向图：Prim&Kruskal
Prim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| //Prim
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T>
void read(T& w)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=103;
const int maxm=maxn*(maxn-1)/2;
int n,m;
struct EDGE
{
int to,nxt,w;
void init(int too,int nxtt,int ww)
{
to=too,nxt=nxtt,w=ww;
}
}edge[maxm<<1];
int ek=0;
int node[maxn];
void addEdge(int from,int too,int ww)
{
edge[++ek].init(too,node[from],ww);
node[from]=ek;
}
void input()
{
read(n),read(m);
int x,y,l;
for(int i=1;i<=m;++i)
{
read(x),read(y),read(l);
if(x!=y)
{
addEdge(x,y,l);
addEdge(y,x,l);
}
}
}
bool operator<(const EDGE& a,const EDGE& b)
{
return a.w<b.w;
}
template<typename T>
struct HEAP
{
T ary[maxm<<1];
int f;
HEAP(){f=0;}
void clear(){f=0;}
bool empty(){return f==0;}
void push(const T& w)
{
ary[++f]=w;
for(int k=f;k!=1&&ary[k]<ary[k/2];k=k/2)
{
Swap(ary[k],ary[k/2]);
}
}
T top(){return ary[1];}
T pop()
{
T tmp=ary[1];
ary[1]=ary[f--];
for(int k=1,son=k*2;son<=f;k=son,son=k*2)
{
if(son+1<=f&&ary[son+1]<ary[son])
son=son+1;
if(ary[son]<ary[k])
Swap(ary[son],ary[k]);
else break;
}
return tmp;
}
};
int s=1;
bool vis[maxn];
HEAP<EDGE> h;
int Prim()
{
int sum=0;
for(int k=2,ff=1;k<=n;++k)
{
vis[ff]=true;
for(int i=node[ff];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(!vis[v])
h.push(edge[i]);
}
EDGE tmp;
for(tmp=h.pop();vis[tmp.to];tmp=h.pop());
ff=tmp.to;
sum+=tmp.w;
}
return sum;
}
int main()
{
input();
printf("%d\n",Prim());
return 0;
}
|
有向图：朱刘算法
概念
最小树形图算法（时间复杂度O(VE)）
即有向图的最小生成树。
定义 选择边集，使得该边集能够让根节点到达所有节点，并使选出的边权和最小
过程
和Kruskal一样，这个算法采取“尝试——调整”的策略来找到答案。
大概过程可以描述为：
对原图G中每个点（除根节点外）选取入边中边权最小的一条入边存储在in[]中，记该入边集与原图顶点构成的子图为G’，将G’先当做最小树形图，设ans=G’的边权和；
如果G’中没有环，G’就是最小树形图；否则只是“边权和最小图”，需要进行调整来使其成为一个树形图。
如何调整？
观察发现，如果G’中有环，那么在G’中一定不存在一条边从环外的点指向这个环中的某个点（环中的点的入边一定来自环内）。
如果要使G’成为一个树形图，要消除环（只要删去环中的一条边即可），同时要将原图G中没有被加入G’的一条边恢复。
设这条边为E(s,t,w)，其中t在环内，s在环外，w为权值。
容易知道这时删去的环中的边一定是in[t]。
看看G’发生了什么改变：
- 将in[t]这条边删去：ans-=edge[in[t]].w
- 将E加入到了G’中：ans+=E.w
但是目前还不知道要调整的是哪一条边。所以这样操作：
对所有可能的E，将E的边权设为E.w-edge[in[t]].w加入G’中，然后在新的图上重复上述步骤，直到不存在环。
下面是具体步骤：
删除自环
略
判定
对原图G中每个点（除根节点外）选取入边中边权最小的一条入边存储在in[]中，并将所有选取的入边权累加到答案中去。
记该入边集与原图顶点构成的子图为G’，
若G’不存在环，则G’就是所求原图的最小树形图。
若G’中存在除根节点外的点的入度为0，则原图不存在最小树形图。
否则继续进行下面的操作。
缩点
将所有的环缩成一个点。
建边
对于缩点后的新图H，添加边的操作如下：
枚举G中所有边E
如果E的起点s和终点t在H中不在同一个点，则添加E’(s,t,E.w-in[t]);
否则直接将E加入H中（或者可以舍弃，因为下一步开始时会删去这样的自环）。
LOOP
将H作为G重复上述操作（所有的），直到判定不存在环为止，此时得到的是某一层的最小树形图。
逐层累加到当前的答案，就是原图的边权和。如果只求边权和的话就可以到此为止了，不过如果要知道原图中最小树形图选取的是哪几条边的话，还要经过展开的操作。
展开
要实现展开的操作，需要在每层加边时记录下每条边对应删去上一层的哪条边。如果在最终的最小树形图中该边被选取，那么上一层中的那条边就不被选取，这样逐层推到最初的原图。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| /*
朱刘算法
*/
typedef long long num;
const num ninf=9223372036854775807ll;
const int maxn=1003;
const int maxm=10003;
int n,m;
struct EDGE
{
int s,t;
num w;
void init(int ss,int tt,num ww)
{
s=ss,t=tt,w=ww;
}
}edge[maxm];
int ek=0;
void addEdge(int k,int v,num w)
{
edge[++ek].init(k,v,w);
}
num in[maxn];
int id[maxn];
int pre[maxn];
int vis[maxn];
num miniTree(int root)
{
num ans=0;
while(true)
{
//初始化
for(int i=1;i<=n;++i)in[i]=ninf;
memset(id+1,0,n*sizeof(int));
memset(pre+1,0,n*sizeof(int));
memset(vis+1,0,n*sizeof(int));
int tid=0;
// 计算in[]
for(int i=1;i<=ek;++i)
{
int u=edge[i].s,v=edge[i].t,w=edge[i].w;
if(u!=v&&edge[i].w<in[v])
{
in[v]=edge[i].w;
pre[v]=u;
}
}
//累加in[]权值到答案，计算pre[]
for(int i=1;i<=n;++i)
{
if(i!=root)
{
if(in[i]<ninf)
ans+=in[i];
else return -1;
}
}
//寻找环，缩点
for(int i=1;i<=n;++i)
{
if(!id[i])
{
int j;
for(j=i;j!=root&&vis[j]!=i&&!id[j];j=pre[j])
vis[j]=i;
if(j!=root&&!id[j])
{
id[j]=++tid;
for(int k=pre[j];k!=j;k=pre[k])
id[k]=tid;
}
if(!id[i])id[i]=++tid;
}
}
if(tid==n)//没有环
return ans;
//更新边
for(int i=1;i<=ek;++i)
{
int u=edge[i].s;
int v=edge[i].t;
edge[i].s=id[u];
edge[i].t=id[v];
if(id[u]!=id[v])
edge[i].w-=in[v];
}
n=tid;
root=id[root];
}
}
|
优化
在原来的代码中，并没有删除自环的操作，而是采取判定的方法解决。
下面的代码删除了自环，减少了每次枚举边的数量，可以在一定程度上加速。
实际上下面的代码并没有“删除自环”，而是在建新图的时候将不是自环的边直接覆盖掉上一层图的边，可以证明代码中的tek<=ek，所以被覆盖的一定是访问过的边。
注意 在原来的代码中，不同的人的in[]有两种不同的用法。有些记录入边的编号，有些直接记录入边的权值。在像这样优化之后，由于边被覆盖，所以用in[]记录编号的方法不能使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| /*
朱刘算法
*/
typedef double num;
const num ninf=;
const int maxn=;
const int maxm=;
int n,m;
struct EDGE
{
int s,t;
num w;
void init(int ss,int tt,num ww)
{
s=ss,t=tt,w=ww;
}
}edge[maxm];
int ek=0;
void addEdge(int k,int v,num w)
{
edge[++ek].init(k,v,w);
}
num in[maxn];
int id[maxn];
int pre[maxn];
int vis[maxn];
num miniTree()
{
num ans=0;
int root=1;
while(true)
{
//初始化
for(int i=1;i<=n;++i)in[i]=ninf;
memset(id+1,0,n*sizeof(int));
memset(pre+1,0,n*sizeof(int)); memset(vis+1,0,n*sizeof(int));
int tek=0,tid=0;
// 计算in[]
for(int i=1;i<=ek;++i)
{
int u=edge[i].s,v=edge[i].t,w=edge[i].w;
if(u!=v&&edge[i].w<in[v])
{
in[v]=edge[i].w;
pre[v]=u;
}
}
//累加in[]权值到答案，计算pre[]
for(int i=1;i<=n;++i)
{
if(i!=root)
{
if(in[i]<ninf)
ans+=in[i];
else return -1;
}
}
//寻找环，缩点
for(int i=1;i<=n;++i)
{
if(!id[i])
{
int j;
for(j=i;j!=root&&vis[j]!=i&&!id[j];j=pre[j])
vis[j]=i;
if(j!=root&&!id[j])
{
id[j]=++tid;
for(int k=pre[j];k!=j;k=pre[k])
id[k]=tid;
}
if(!id[i])id[i]=++tid;
}
}
if(tid==n)//没有环
return ans;
//更新边
for(int i=1;i<=ek;++i)
{
int u=edge[i].s,v=edge[i].t;
if(id[u]!=id[v])
edge[++tek].init(id[u],id[v],edge[i].w-in[v]);
}
n=tid;
ek=tek;
}
}
|
不固定根
如果题目给出的图并没有一个确定的根，可以这样处理：
新建一个超级根，和每个点连权为sumw+1的边，再用上面的算法处理，最后将答案减去(sumw+1)。
如果要求实际选取哪个点作为根：
首先可以知道的是，在最终的最小树形图中：
如果超级根有不止一条出边，那么原图不存在最小树形图（否则花费这么大的代价选择另一条出边）；
如果只有一条出边，那么这条出边对应的点就是实际的根。
在这时，由于经过了许多次缩点的操作，得到的根不一定就是原图中的点。但是思考之前朱刘算法的过程，发现边并没有增加或减少，而且如果原图中的一条边连接了某个点，那么在最终的图中，这条边连接的点展开之后一定包含这个点。
所以如果在最终的树形图中，超级根的出边对应最初连接的原图中的点，就是所求的实际根。
但是还有一个问题：所有的边都已经被修改了。
回头去看之前为超级根添加出边的操作，过程大概是这样的：
1
2
3
4
| for(int i=1;i<=n;++i)//假设新建superRoot作为超级根
{
addEdge(superRoot,i,sumw);//添加一条superRoot指向i,边权为sumw的有向边
}
|
假设在代码中用m记录原图中边的个数，那么原图中本来就存在的边为edge[1m]，现在添加的这些边对应就是第edge[(m+1)(m+n)]条，而终点为i的边就是edge[m+i]。
那么假设最后找到超级根的出边为edge[x]，最初的终点就是(x-m)这个点，也就是所求的实际根。
需要注意的是，由于这里利用的边的编号的性质，所以不能使用前面提到的滚动覆盖边的优化。
代码
下面是可供参考的主要代码。
请特别注意其中用蓝色底纹加下划线突出强调的语句，这两句代码找到最终最小树形图中超级根的最后一个出边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| typedef int num;
num in[maxn];
int id[maxn];
int pre[maxn];
int vis[maxn];
int rootEdge;
num miniTree(int root,int n)
{
num ans=0;
while(true)
{
//初始化
for(int i=1;i<=n;++i)in[i]=ninf;
memset(id+1,0,n*sizeof(int));
memset(pre+1,0,n*sizeof(int));
memset(vis+1,0,n*sizeof(int));
int tid=0;
// 计算in[]
for(int i=1;i<=ek;++i)
{
int u=edge[i].s,v=edge[i].t,w=edge[i].w;
if(u!=v&&edge[i].w<in[v])
{
in[v]=edge[i].w;
pre[v]=u;
if(u==root)
rootEdge=i;
}
}
//累加in[]权值到答案，计算pre[]
for(int i=1;i<=n;++i)
{
if(i!=root)
{
if(in[i]<ninf)
ans+=in[i];
else return -1;
}
}
//寻找环，缩点
for(int i=1;i<=n;++i)
{
if(!id[i])
{
int j;
for(j=i;j!=root&&vis[j]!=i&&!id[j];j=pre[j])
vis[j]=i;
if(j!=root&&!id[j])
{
id[j]=++tid;
for(int k=pre[j];k!=j;k=pre[k])
id[k]=tid;
}
if(!id[i])id[i]=++tid;
}
}
if(tid==n)//没有环
return ans;
//更新边
for(int i=1;i<=ek;++i)
{
int u=edge[i].s;
int v=edge[i].t;
edge[i].s=id[u];
edge[i].t=id[v];
if(id[u]!=id[v])
edge[i].w-=in[v];
}
n=tid;
root=id[root];
}
}
num ans;
int realroot;
void solve()
{
int superRoot=n+1;
for(int i=1;i<=n;++i)
addEdge(superRoot,i,sumw+1);
ans=miniTree(superRoot,n+1);
if(ans>(sumw+1)*2)//如果答案超过两倍的sumw，说明选取了不止一条超级根出发的边
ans=-1;
else
{
ans=ans-(sumw+1);
realroot=rootEdge-m;
}
}
|
练习题
