也许是吧
首先
明显的,不论是prim还是kruskal,都是可以生成所有最小生成树的,只要精心构造一下输入边的顺序即可。
所以,我们可以精心构造边的顺序使得两次生成的最小生成树不一样,这就可以作为最小生成树不唯一的充分条件。 (充分必要条件?也许是吧,能A就行)
于是
众所周知,在kruskal中,可以作为最小生成树边但没有被选上的边纯粹是运气不好,被心情不好的sort排到了后面。
那么,我们可以用一种巧妙的办法,使得两次kruskal中相同权值的边翻转一下,这样一条可能的边一定会去到占用它位置的边的前面。
为了区分任意两条边,我们给每一条边打一个唯一的时间戳,在排序时以第二关键字参与排序。一次顺序,一次倒序,这样就可以使得相同权值的边的顺序反转。然后再做一遍最小生成树,如果不一样,那么说明最小生成树不唯一。
当然,也可以手动处理出每个权值的范围,直接翻转,会跑得快一些。
那么
上代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct arc{
int x,y,z,key;
bool used;
}a[200010];
int t,n,m,s[100010];
bool comp1(arc a,arc b){
return(a.z<b.z||(a.z==b.z&&a.key<b.key));
}
bool comp2(arc a,arc b){
return(a.z<b.z||(a.z==b.z&&a.key>b.key));
}
template<typename T>void read(T &x){
char c=getchar();
for(;c<33;c=getchar());
for(x=0;(47<c)&&(c<58);x=x*10+c-48,c=getchar());
}
int root(int m){
if(s[m]){
return(s[m]=root(s[m]));
}
return(m);
}
void uni(int x,int y){
s[root(y)]=root(x);
}
int main(){
for(read(t);t;t--){
read(n);read(m);
for(int i=1;i<=m;i++){
read(a[i].x);read(a[i].y);read(a[i].z);
a[i].used=0;
a[i].key=i;
}
sort(a+1,a+m+1,comp1);
memset(s,0,sizeof(s));
long long ans=0,v=0;
for(int i=1,j=0;i<n;i++){
for(j++;j<=m&&root(a[j].x)==root(a[j].y);j++);
uni(a[j].x,a[j].y);
ans+=a[j].z;
a[j].used=1;
}
sort(a+1,a+m+1,comp2);
memset(s,0,sizeof(s));
for(int i=1,j=0;i<n;i++){
for(j++;j<=m&&root(a[j].x)==root(a[j].y);j++);
uni(a[j].x,a[j].y);
if(!a[j].used){
v=1;
break;
}
}
printf("%lld
",ans);
printf(v?"No
":"Yes
");
}
}
2020/8/4 update:
显然这个东西的正确性是有问题的
????/?/? update:
显然按照是否被用过来排序就对了