【POJ 1679 The Unique MST】最小生成树-阿里云开发者社区

【POJ 1679 The Unique MST】最小生成树

2015-11-10 1128

简介： 无向连通图（无重边），判断最小生成树是否唯一，若唯一求边权和。分析生成树的生成过程，只有一个圈内出现权值相同的边才会出现权值和相等但“异构”的生成树。（并不一定是最小生成树）分析贪心策略求最小生成树的过程（贪心地选最短的边来扩充已加入生成树的顶点集合U），发现只有当出现“U中两个不同的点到V-U中同一点的距离同时为当前最短边”时，才会出现“异构”的最小生成树。

+关注继续查看

无向连通图（无重边），判断最小生成树是否唯一，若唯一求边权和。

分析生成树的生成过程，只有一个圈内出现权值相同的边才会出现权值和相等但“异构”的生成树。（并不一定是最小生成树）

分析贪心策略求最小生成树的过程（贪心地选最短的边来扩充已加入生成树的顶点集合U），发现只有当出现“U中两个不同的点到V-U中同一点的距离同时为当前最短边”时，才会出现“异构”的最小生成树。

上图为kruscal和prim生成过程中可能遇到的相等边的情况，红色和蓝色的为权值相等的边。

可以看到kruscal由于事先将所有边按权值排序，所以在构造MST的过程中，当发现权值相同的边时，需要遍历之前遇到过的所有相同权值的边来判断是否发生“争抢同一点”的情况，若发现即可判定存在“异构”最小生成树。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int MAX_N=105;
 6 const int MAX_M=5005;
 7 
 8 int par[MAX_N];
 9 void init()
10 {
11     memset(par,-1,sizeof(par));
12 }
13 int find(int x)
14 {
15     if(par[x]==-1) return x;
16     return par[x]=find(par[x]);
17 }
18 void unite(int x,int y)
19 {
20     x=find(x);
21     y=find(y);
22     if(x!=y) par[x]=y;
23 }
24 bool same(int x,int y)
25 {
26     return find(x)==find(y);
27 }
28 
29 int t;
30 int n,m;
31 struct Edge
32 {
33     int u,v,w;
34 }e[MAX_M];
35 
36 bool cmp(Edge e1,Edge e2)
37 {
38     return e1.w<e2.w;
39 }
40 
41 bool inter(Edge e1,Edge e2)
42 {
43     if(e1.u==e2.u||e1.u==e2.v||e1.v==e2.u||e1.v==e2.v) return true;
44     else return false;
45 }
46 
47 int kruscal()
48 {
49     int ans=0;
50     init();
51     ans+=e[0].w;
52     unite(e[0].u,e[0].v);
53     int cur_w=e[0].w;
54     for(int i=1;i<m;i++)
55     {
56         if(same(e[i].u,e[i].v))
57         {
58             for(int j=i-1;e[j].w==e[i].w;j--)
59             {
60                 if(inter(e[i],e[j]))//判两条边有无交点
61                 {
62                     ans=-1;
63                     break;
64                 }
65             }
66         }else
67         {
68             unite(e[i].u,e[i].v);
69             ans+=e[i].w;
70             cur_w=e[i].w;
71         }
72     }
73     return ans;
74 }
75 
76 int main()
77 {
78     freopen("1679.txt","r",stdin);
79     scanf("%d",&t);
80     while(t--)
81     {
82         scanf("%d%d",&n,&m);
83         for(int i=0;i<m;i++)
84         {
85             scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
86         }
87         if(n==1) {printf("0\n"); continue;}
88         sort(e,e+m,cmp);
89         int ans=kruscal();
90         if(ans==-1)
91             printf("Not Unique!\n");
92         else printf("%d\n",ans);
93     }
94     return 0;
95 }

kruscal

而prim由于每次都选连结U和V-U的边，所以不会遇到kruscal那样蓝色的可能误判的边（我开始就WA在这里），因此只需在加入一个新点更新其他点的mincost时判断有没有和mincost值相等的另一条边的即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <queue>
 5 using namespace std;
 6 const int MAX_N=105;
 7 const int MAX_M=5005;
 8 const int INF=100000;
 9 typedef pair<int,int> P;//cost,to
10 struct Edge
11 {
12     int to,cost;
13     Edge(){}
14     Edge(int tt,int cc):to(tt),cost(cc){}
15 };
16 int t;
17 int n,m;
18 vector<Edge> G[MAX_N];
19 int vis[MAX_N];
20 int mincost[MAX_N];
21 
22 int prim()
23 {
24     int ans=0;
25     int flag=0;
26     priority_queue<P,vector<P>,greater<P> > que;
27     memset(vis,0,sizeof(vis));
28     for(int i=1;i<=n;i++) mincost[i]=INF;
29     que.push(P(0,1));
30     mincost[1]=0;
31     while(!que.empty())
32     {
33         P p=que.top();
34         que.pop();
35         int v=p.second;
36         if(vis[v]||mincost[v]<p.first) continue;
37         vis[v]=1;
38         mincost[v]=p.first;
39         ans+=mincost[v];
40         for(int i=0;i<G[v].size();i++)
41         {
42             int u=G[v][i].to;
43             if(!vis[u])
44             {
45                 if(mincost[u]>G[v][i].cost&&G[v][i].cost<INF)
46                 {
47                     mincost[u]=G[v][i].cost;
48                     que.push(P(mincost[u],u));
49                 }else if(mincost[u]==G[v][i].cost)//存在到达点u权值相等且都为最小值的边
50                 {
51                     flag=1;
52                     break;
53                 }
54             }
55         }
56         if(flag) break;
57     }
58     if(flag) ans=-1;
59     return ans;
60 }
61 int main()
62 {
63     freopen("1679.txt","r",stdin);
64     scanf("%d",&t);
65     while(t--)
66     {
67         scanf("%d%d",&n,&m);
68         for(int i=1;i<=n;i++) G[i].clear();
69         for(int i=0;i<m;i++)
70         {
71             int u,v,w;
72             scanf("%d%d%d",&u,&v,&w);
73             G[u].push_back(Edge(v,w));
74             G[v].push_back(Edge(u,w));
75         }
76         if(n==1) {printf("0\n"); continue;}
77         int ans=prim();
78         if(ans==-1)
79             printf("Not Unique!\n");
80         else printf("%d\n",ans);
81     }
82     return 0;
83 }

prim_priorityqueue