pat-top 1016. Uniqueness of MST (35)

https://www.patest.cn/contests/pat-t-practise/1016

照抄了 http://blog.csdn.net/jtjy568805874/article/details/60338730

确定是否唯一是难点，在每新加一个边时，先看同等权值的边可否加入，并对所有可加入的边进行计数，最后如果边数小于n，不小于则最小生成树不唯一。

#include <cstdio>
#include <algorithm>
#include <vector>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define intwo(i,j) scanf("%d%d",&i,&j)
#define inthree(i,j,k) scanf("%d%d%d",&i,&j,&k)
using namespace std;
const int maxn = 3e5 + 10;
int n, m;
int fa[maxn];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
typedef struct e {
int x, y, w;
bool friend operator < (struct e a, struct e b) {
return a.w < b.w;
}
}E;
E es[maxn];
int main()
{
intwo(n, m);
int mCost = 0, tot = 0, nCompt = n; //tot 可出现在最小生成树中的边的个数
rep(i, 1, n) fa[i] = i;
rep(i, 1, m) inthree(es[i].x, es[i].y, es[i].w);
sort(es + 1, es + m + 1);
for (int i = 1, j; i <= m; i = j)
{
for (j = i; j <= m&&es[i].w == es[j].w; j++)
{
int fx = find(es[j].x), fy = find(es[j].y);
if (fx == fy) continue; else tot++;
}
for (j = i; j <= m&&es[i].w == es[j].w; j++)
{
int fx = find(es[j].x), fy = find(es[j].y);
if (fx == fy) continue;
fa[fx] = fy; mCost += es[j].w; nCompt--;
}
}
if (nCompt == 1) printf("%dn%sn", mCost, tot < n ? "Yes" : "No");
else printf("No MSTn%dn", nCompt);
return 0;
}

最后

以上就是细心萝莉为你收集整理的pat-top 1016. Uniqueness of MST (35)的全部内容，希望文章能够帮你解决pat-top 1016. Uniqueness of MST (35)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。