深刻理解kruskal算法是关键，采用最小与次小生成树同步更新，实现次小生成树求解：
  Code
1 #include "stdio.h"
2#include <algorithm>
3using namespace std;
4#define M 10001
5#define N 101
6struct Edge
7 {
8 int u;
9 int v;
10 int w;
11 };
12Edge e[M];
13int n,m;
14int prt[N];
15int map[N][N];
16int grh[N][N];
17int d[N][N];
18bool flag[N][N];
19int gn[N];
20int en=0;
21int s;
22
23bool cmp(const Edge &a,const Edge &b)
24{
25 return a.w<b.w;
26}
27
28int Find(int x)
29{
30 int p;
31 if(x==prt[x])
32  {
33 return x;
34 }
35 p=Find(prt[x]);
36 prt[x]=p;
37 return p;
38}
39
40int Union(int x,int y,int w)
41{
42 int p,q;
43 p=Find(x);
44 q=Find(y);
45 if(p==q)
46 {
47 return 0;
48 }
49 prt[p]=q;
50 return 1;
51}
52
53
54void dfs(int max,int v)
55{
56 int i;
57 d[s][v]=max;
58 d[v][s]=max;
59 for(i=0;i<gn[v];i++)
60 {
61 if(grh[v][map[v][i]]>max)
62 {
63 dfs(grh[v][map[v][i]],map[v][i]);
64 }
65 else
66 dfs(max,map[v][i]);
67 }
68}
69bool DDD()
70{
71 int i,j;
72 for(i=1;i<=n;i++)
73 {
74 s=i;
75 d[i][i]=0;
76 dfs(0,s);
77 }
78 for(i=1;i<=n;i++)
79 {
80 for(j=1;j<=n;j++)
81 {
82 if(!flag[i][j])
83 {
84 if(d[i][j]==grh[i][j])
85 {
86 return false;
87 }
88 }
89 }
90 }
91 return true;
92}
93
94void Kruskal()
95{
96 int i,tmp,t;
97 int ans=0;
98 for(i=1;i<=n;i++)
99 {
100 prt[i]=i;
101 }
102 for(i=0;i<m;i++)
103 {
104 tmp=Union(e[i].u,e[i].v,e[i].w);
105 if(tmp>0)
106 {
107 ans+=e[i].w;
108 t=gn[e[i].u];
109 map[e[i].u][t]=e[i].v;
110 flag[e[i].u][e[i].v]=true;
111 gn[e[i].u]++;
112 }
113 }
114 if(DDD())
115 printf("%d\n",ans);
116 else printf("Not Unique!\n");
117}
118
119int main()
120{
121 int i,T;
122 scanf("%d",&T);
123 while(T--)
124 {
125 scanf("%d %d",&n,&m);
126 memset(gn,0,sizeof(gn));
127 memset(flag,false,sizeof(flag));
128 memset(grh,-1,sizeof(grh));
129 memset(d,127,sizeof(d));
130 for(i=0;i<m;i++)
131 {
132 scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
133 grh[e[i].u][e[i].v]=e[i].w;
134 }
135 sort(e,e+m,cmp);
136 Kruskal();
137 }
138 return 0;
139}
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 26 | 27 | 28 | 29 | 30 | 31 | 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 | 1 | | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|
导航
统计
常用链接
留言簿
随笔分类(1)
随笔档案(2)
文章分类(15)
文章档案(7)
搜索
最新评论
阅读排行榜
评论排行榜
|
|