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

简介: 无向连通图(无重边),判断最小生成树是否唯一,若唯一求边权和。 分析生成树的生成过程,只有一个圈内出现权值相同的边才会出现权值和相等但“异构”的生成树。(并不一定是最小生成树) 分析贪心策略求最小生成树的过程(贪心地选最短的边来扩充已加入生成树的顶点集合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

 

目录
相关文章
|
13天前
|
算法 定位技术
The Unique MST(最小生成树的唯一路径)
The Unique MST(最小生成树的唯一路径)
|
13天前
|
人工智能 BI
【每日一题Day324】LC1462课程表 IV | BFS 拓扑排序 Floyd
【每日一题Day324】LC1462课程表 IV | BFS 拓扑排序 Floyd
17 0
UPC Graph (最小生成树 || 并查集+二分)
UPC Graph (最小生成树 || 并查集+二分)
73 0
HDU7050.Link with Limit(有向图tarjan找环)
HDU7050.Link with Limit(有向图tarjan找环)
108 0
|
机器学习/深度学习 人工智能 BI
codeforces-1242-B 0-1 MST
B. 0-1 MST time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Ujan has a lot of useless stuff in his drawers, a considerable part of which are his math notebooks: it is time to sort them out.
141 0
codeforces-1242-B 0-1 MST

热门文章

最新文章