学步园

求给定图的次小生成树。

对于给定的图，我们可以证明，次小生成树可以由最小生成树变换一边得到。那么我们可以如下求给定图的次小生成树。首先，我们用prime算法求出图的最小生成树，在这个过程中记录每条边是否用过，以及两个点之间最短路径上的最大权值F[i,j]

F[i,j]可以如此求得，当加入点u的时候，并且u的父结点是v 那么对于已经在生成树中的节点x

F[x,u] = max(F[x,v], weight[u][v])，那么我么就可以用Prime算法一样的时间复杂度来求出图的次小生成树。如下是我的代码，通过了uva 10600：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=18&problem=1541&mosmsg=Submission+received+with+ID+7266392

#include "iostream"<br /> #include "cstdio"<br /> #include "cstring"<br /> #define EXIST 1<br /> #define NOT_EXIST 0<br /> #define USE 2<br /> using namespace std;<br /> const int MaxN = 110;<br /> const int Inf = 0x7fffffff;<br /> int g[MaxN][MaxN];<br /> int N,M;<br /> char use[MaxN][MaxN];<br /> int ans1,ans2,F[MaxN][MaxN];<br /> int prime(){<br /> int dis[MaxN];<br /> bool vis[MaxN];<br /> int pre[MaxN];<br /> memset(pre,0xff,sizeof(pre));<br /> memset(vis,false,sizeof(vis));<br /> for(int i = 0 ;i < MaxN; ++i)<br /> dis[i] = Inf;<br /> dis[1] = 0;<br /> for(int i = 1; i <= N; ++i){<br /> int pos;<br /> int tmp = Inf;<br /> for(int j = 1;j <= N; ++j){<br /> if(!vis[j] && dis[j] < tmp){<br /> tmp = dis[j];<br /> pos = j;<br /> }<br /> }<br /> if(pre[pos] != -1){<br /> use[pre[pos]][pos] = use[pos][pre[pos]] = USE;<br /> for(int j = 1;j <= N; ++j){<br /> if(vis[j])<br /> F[j][pos] = max(F[j][pre[pos]],g[pre[pos]][pos]);<br /> }<br /> }<br /> vis[pos] = true;<br /> ans1 += dis[pos];<br /> for(int j = 1;j <= N; ++j){<br /> if(!vis[j] && g[pos][j]!= 0 && g[pos][j] < dis[j]){<br /> dis[j] = g[pos][j];<br /> pre[j] = pos;<br /> }<br /> }<br /> }<br /> return ans1;<br /> }<br /> int Second_MST(){<br /> ans2 = Inf;<br /> for(int i = 1;i <= N; ++i){<br /> for(int j = 1;j <= N; ++j){<br /> if(use[i][j] == EXIST){<br /> if(ans1 + g[i][j] - F[i][j] < ans2)<br /> ans2 = ans1 + g[i][j] - F[i][j];<br /> }<br /> }<br /> }<br /> return ans2;<br /> }<br /> int main(){<br /> int T;<br /> scanf("%d",&T);<br /> while(T--){<br /> memset(g,0,sizeof(g));<br /> memset(use,0,sizeof(use));<br /> memset(F,0,sizeof(F));<br /> ans1 = ans2 = 0;<br /> scanf("%d%d",&N,&M);<br /> for(int i = 0 ;i < M; ++i){<br /> int A,B,C;<br /> scanf("%d%d%d",&A,&B,&C);<br /> g[A][B] = g[B][A] = C;<br /> use[A][B] = use[B][A] = EXIST;<br /> }<br /> printf("%d ",prime());<br /> printf("%d/n",Second_MST());<br /> }<br /> return 0;<br /> }<br />  

在代码中用use[i][j] 表示边i,j是否用过，1表示存在，但没有用过，0表示不存在，2表示存在，并且已经在最小生成树中。