次小生成树

    最小生成树的算法想必大家都很了解，主要有kruskal和prim。但如果要求次小生成树(即第二小的生成树)呢？

    一种容易想到的方法是枚举删除最小生成树上的边，再求最小生成树。用kruskal这种算法的复杂度为O(n*elog2e)，当图比较稠密时，复杂度接近O(n^3)。

    但有一种更简单的方法：先求最小生成树T，枚举添加不在T中的边，则添加后一定会形成环。找到环上边值第二大的边(即环中属于T中的最大边)，把它删掉，计算当前生成树的权值，取所有枚举修改的生成树的最小值，即为次小生成树。

    这种方法在实现时有更简单的方法：首先求最小生成树T，然后从每个结点u遍历最小生成树T，用一个二维数组max[u][v]记录结点u到结点v的路劲上边的最大值(即最大边的值)。然后枚举不在T中的边(u,v)，计算T- max[u][v] + w(u,v)的最小值，即为次小生成树的权值。显然，这种方法的时间复杂度为O(n^2 + e)。

    可见，第二种算法将原来的时间复杂度O(n^3)提高到了O(n^2)。

 

    例：判断生成树的唯一性，唯一则输出权值，不唯一输出Not Unique!(POJ1679)

显然，可以转化为求次小生成树，次小生成树权值=最小生成树，则不唯一。

#include <iostream>
#include <algorithm>
#include <queue>
const int INF = 0x7fffffff;
const int MAX = 10001;
int n,m;
int num;
int p[MAX];
int max[101][101];

struct Edge		//原始图
{
	int from;
	int to;
	int w;
	bool flag;
}e[MAX];

struct Tree		//最小生成树
{
	int to;
	int w;
	int next;
}tree[202];
int index[101];

struct Node		//生成树的结点
{
	int seq;	//结点编号
	int max;	//从某个点到它的路径中的最大边的长度
};

bool cmp(const Edge &a, const Edge &b)
{
	return a.w < b.w;
}

void makeSet()
{
	for(int i = 0; i <= n; i++)
	{
		p[i] = i;
	}
}

int findSet(int x)
{
	if(x != p[x])
		p[x] = findSet(p[x]);
	return p[x];
}

void addEdge(int from, int to, int w)
{
	tree[num].to = to;
	tree[num].w = w;
	tree[num].next = index[from];
	index[from] = num++;
}

int kruscal()
{
	int i,j;
	int x, y;
	int edgeNum = 0;
	int result = 0;
	makeSet();
	std::sort(e,e+m,cmp);
	for(i = 0; i < m; i++)
	{
		x = findSet(e[i].from);
		y = findSet(e[i].to);
		if(x != y)
		{
			edgeNum++;
			addEdge(e[i].from,e[i].to,e[i].w);
			addEdge(e[i].to,e[i].from,e[i].w);
			e[i].flag = true;
			p[x] = y;
			result += e[i].w;
		}
	}
	return edgeNum == n-1 ? result : -1;
}

void bfs(int p)
{
	int i,j;
	bool used[101];
	memset(used,0,sizeof(used));
	std::queue<Node> que;
	Node now,adj;
	now.max = 0;
	now.seq = p;
	que.push(now);
	used[p] = true;
	while(!que.empty())
	{
		Node q = que.front();
		que.pop();
		for(i = index[q.seq]; i != -1; i = tree[i].next)
		{
			adj.seq = tree[i].to;
			adj.max = tree[i].w;
			if(!used[adj.seq])
			{
				if(q.max > adj.max)
					adj.max = q.max;
				max[p][adj.seq] = adj.max;
				used[adj.seq] = true;
				que.push(adj);
			}
		}
	}
}

void second_MST()
{
	int i,j;
	int mst = kruscal();
	for(i = 1; i <= n; i++)
		bfs(i);
	int smst = INF;
	for(i = 0; i < m; i++)
	{
		if(!e[i].flag)
		{
			if(mst + e[i].w - max[e[i].from][e[i].to] < smst)
				smst = mst + e[i].w - max[e[i].from][e[i].to];
		}
	}
	if(smst == mst)
		printf("Not Unique!\n");
	else
		printf("%d\n",mst);
}

int main()
{
	int i,j;
	int cases;
	int a,b,w;
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%d %d",&n,&m);
		for(i = 0; i < m; i++)
		{
			scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].w);
			e[i].flag = false;
		}
		num = 0;
		memset(index,-1,sizeof(index));
		second_MST();
	}
	return 0;
}

 

 

 

 

 

评论

2 楼 Skyming 2012-04-23  

顶，讲的简单明了

1 楼 sgeteternal 2011-08-26  

今天开始做次小生成树，启蒙课啊！