网上两种算法对应都有:
题目链接
prim算法判最小生成树是否唯一
下面是这道题的AC代码:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=105;
const int inf=1e9;
int cas=1;
int n,m;
int mapp[maxn][maxn],vis[maxn],dis[maxn];
void prim(int u)
{
CLR(vis);
int flag=0,sum=0;
for(int i=1;i<=n;i++)
dis[i]=mapp[u][i];
vis[u]=1;
for(int i=1;i<=n;i++){
int minn=inf;
int v=-1;
for(int j=1;j<=n;j++){
if(!vis[j] && minn>dis[j]){
v = j;
minn = dis[j];
}
}
if(v!=-1){ //如果v=-1了,说明这个图已经连通了,不用再判断下去了,当然也可以直接break掉,一样的.
//printf("%d %d\n",v,minn);
int ans=0; //记录相同权值的边有几条,把图画出来就懂的起了!!!
for(int j=1;j<=n;j++){
if(vis[j] && mapp[v][j] == minn) //这一步处理的非常好.
ans++;
}
if(ans>1){ //如果大于1,说明用其他路也能达到该点,所以树就不唯一了,所以可以直接break了.
flag=1;
break;
}
sum+=minn;
vis[v]=1;
for(int j=1;j<=n;j++){
if(!vis[j] && dis[j] > mapp[v][j])
dis[j] = mapp[v][j];
}
}
}
if(flag)
printf("Not Unique!\n");
else
printf("%d\n",sum);
}
int main()
{
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) mapp[i][j]=0;
else mapp[i][j]=inf;
}
}
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
mapp[u][v] = mapp[v][u] = w;
}
prim(1); //从点 1 开始找.
}
}
kruskal的算法,再用这个算法时有一点要特别注意,否则会一直WA,就是在进行删边操作时,注意删完或需要判断这个图是否是一个树!!!，如果不是的话返回-1或最大值,不要返回sum值,因为删去边后没有树的话,则最小生成树还是唯一的!!!
AC代码:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn = 1e5+5;
int pre[105];
int n,m;
vector<int>used;
struct node{ int u,v,w;} s[maxn];
void init(){ for(int i=0;i<=n;i++) pre[i]=i; }
int Find(int x){ return pre[x]==x?x:pre[x]=Find(pre[x]); }
bool cmp(node a,node b){ return a.w<b.w; }
int kruskal(int flag)
{
int num=0;
int sum=0;
for(int i=0;i<m;i++){
if(i==flag) continue;
int u=Find(s[i].u);
int v=Find(s[i].v);
if( u != v){
pre[v]=u;
sum+=s[i].w;
num++;
if(flag==-1)
used.push_back(i);
}
if(num==n-1)
break;
}
int cnt=0; //一定判断一下树是否联通!!!
for(int i=1;i<=n;i++){
if(pre[i]==i)
cnt++;
}
if(cnt>1)
return -1;
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
CLR(s);
scanf("%d %d",&n,&m);
init();
used.clear(); //不要忘了清空!!!
for(int i=0;i<m;i++){
scanf("%d %d %d",&s[i].u,&s[i].v,&s[i].w);
}
sort(s,s+m,cmp);
int ans=kruskal(-1);
int flag=0;
for(int i=0;i<used.size();i++){
init();
int p=0;
p=kruskal(used[i]);
if(p==ans){
flag=1;
break;
}
}
if(flag)
printf("Not Unique!\n");
else
printf("%d\n",ans);
}
}
