【POJ1697】次小生成树

题目大意：让你求最小生成树，并判断最小生成树是否唯一。

解题思路：本题其实是想让你求次小生成树，如果次小生成树和最小生成树权值和相等，最小生成树则不唯一，否则唯一。

解题步骤：

1、先求最小生成树，求最小生成树过程中标记出现在最小生成树中的边以及fp[i][j]，fp数组保存的是最小生成树上从i到j的最大权值。

2、枚举所有未出现在最小生成树中的边map[i][j]，找到tp=（map[i][j]-fp[i][j]）差值最小的进行替换，为什么可以这样？因为加入map[i][j]到最小生成树中后必形成环，然后消去环中非map[i][j]的最大权值边，得到的解必为最优解。

3、tp==0则最小生成树不唯一，否则唯一。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <queue>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 const int maxn=110;
10 const int oo=0x3fffffff;
11 int lowcost[maxn], visit[maxn], map[maxn][maxn], used[maxn][maxn], pre[maxn], fp[maxn][maxn]; ///fp数组保存的是最小生成树上从i到j的最大权值边
12 int n, m, T;
13 
14 int Prim()
15 {
16     int sum=0;
17     for(int i=1; i<=n; i++) lowcost[i]=oo, pre[i]=0, visit[i]=0;
18     lowcost[1]=0;
19     for(int i=1; i<=n; i++)
20     {
21         int k=-1, minn=oo;
22         for(int j=1; j<=n; j++)
23             if(minn>lowcost[j]&&!visit[j]) k=j, minn=lowcost[j];
24         if(k==-1) break;
25         if(pre[k]!=0)     ///源点不考虑进去
26         {
27             used[pre[k]][k]=used[k][pre[k]]=2; ///出现在最小生成树中的边标记一下
28             for(int j=1; j<=n; j++)
29                 if(visit[j]) fp[j][k]=max(fp[j][pre[k]],map[pre[k]][k]); ///找生成树中已出现的节点j，求j到k路上最大权值边
30         }
31         visit[k]=1;
32         sum+=lowcost[k];
33         lowcost[k]=0;
34         for(int j=1; j<=n; j++)
35             if(!visit[j]&&lowcost[j]>map[k][j])
36             {
37                 pre[j]=k;
38                 lowcost[j]= map[k][j];
39             }
40     }
41     return sum;
42 }
43 
44 void Solve()
45 {
46     int ans=Prim();
47     int tp=oo;
48     for(int i=1; i<=n; i++)
49         for(int j=1; j<=n; j++)
50            if(used[i][j]==1) tp=min(tp,map[i][j]-fp[i][j]); ///枚举未出现在生成树中的边
51     if(tp==0) puts("Not Unique!");
52     else printf("%d\n",ans);
53 }
54 
55 int main()
56 {
57     cin >> T;
58     while(T--)
59     {
60         scanf("%d%d",&n,&m);
61         for(int i=1; i<=n; i++)
62             for(int j=1; j<=n; j++) fp[i][j]=used[i][j]=0, map[i][j]=oo;
63         for(int i=0; i<m; i++)
64         {
65             int u, v, val;
66             scanf("%d%d%d",&u,&v,&val);
67             map[u][v]=map[v][u]=val;
68             used[u][v]=used[v][u]=1;
69         }
70         Solve();
71     }
72     return 0;
73 }