无向连通图（无重边），判断最小生成树是否唯一，若唯一求边权和。
分析生成树的生成过程，只有一个圈内出现权值相同的边才会出现权值和相等但“异构”的生成树。（并不一定是最小生成树）
分析贪心策略求最小生成树的过程（贪心地选最短的边来扩充已加入生成树的顶点集合U），发现只有当出现“U中两个不同的点到V-U中同一点的距离同时为当前最短边”时，才会出现“异构”的最小生成树。
上图为kruscal和prim生成过程中可能遇到的相等边的情况，红色和蓝色的为权值相等的边。
可以看到kruscal由于事先将所有边按权值排序，所以在构造MST的过程中，当发现权值相同的边时，需要遍历之前遇到过的所有相同权值的边来判断是否发生“争抢同一点”的情况，若发现即可判定存在“异构”最小生成树。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N=;
const int MAX_M=; int par[MAX_N];
void init()
{
memset(par,-,sizeof(par));
}
int find(int x)
{
if(par[x]==-) return x;
return par[x]=find(par[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y) par[x]=y;
}
bool same(int x,int y)
{
return find(x)==find(y);
} int t;
int n,m;
struct Edge
{
int u,v,w;
}e[MAX_M]; bool cmp(Edge e1,Edge e2)
{
return e1.w<e2.w;
} bool inter(Edge e1,Edge e2)
{
if(e1.u==e2.u||e1.u==e2.v||e1.v==e2.u||e1.v==e2.v) return true;
else return false;
} int kruscal()
{
int ans=;
init();
ans+=e[].w;
unite(e[].u,e[].v);
int cur_w=e[].w;
for(int i=;i<m;i++)
{
if(same(e[i].u,e[i].v))
{
for(int j=i-;e[j].w==e[i].w;j--)
{
if(inter(e[i],e[j]))//判两条边有无交点
{
ans=-;
break;
}
}
}else
{
unite(e[i].u,e[i].v);
ans+=e[i].w;
cur_w=e[i].w;
}
}
return ans;
} int main()
{
freopen("1679.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
if(n==) {printf("0\n"); continue;}
sort(e,e+m,cmp);
int ans=kruscal();
if(ans==-)
printf("Not Unique!\n");
else printf("%d\n",ans);
}
return ;
}
kruscal
而prim由于每次都选连结U和V-U的边，所以不会遇到kruscal那样蓝色的可能误判的边（我开始就WA在这里），因此只需在加入一个新点更新其他点的mincost时判断有没有和mincost值相等的另一条边的即可。
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N=;
const int MAX_M=;
const int INF=;
typedef pair<int,int> P;//cost,to
struct Edge
{
int to,cost;
Edge(){}
Edge(int tt,int cc):to(tt),cost(cc){}
};
int t;
int n,m;
vector<Edge> G[MAX_N];
int vis[MAX_N];
int mincost[MAX_N]; int prim()
{
int ans=;
int flag=;
priority_queue<P,vector<P>,greater<P> > que;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++) mincost[i]=INF;
que.push(P(,));
mincost[]=;
while(!que.empty())
{
P p=que.top();
que.pop();
int v=p.second;
if(vis[v]||mincost[v]<p.first) continue;
vis[v]=;
mincost[v]=p.first;
ans+=mincost[v];
for(int i=;i<G[v].size();i++)
{
int u=G[v][i].to;
if(!vis[u])
{
if(mincost[u]>G[v][i].cost&&G[v][i].cost<INF)
{
mincost[u]=G[v][i].cost;
que.push(P(mincost[u],u));
}else if(mincost[u]==G[v][i].cost)//存在到达点u权值相等且都为最小值的边
{
flag=;
break;
}
}
}
if(flag) break;
}
if(flag) ans=-;
return ans;
}
int main()
{
freopen("1679.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) G[i].clear();
for(int i=;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u].push_back(Edge(v,w));
G[v].push_back(Edge(u,w));
}
if(n==) {printf("0\n"); continue;}
int ans=prim();
if(ans==-)
printf("Not Unique!\n");
else printf("%d\n",ans);
}
return ;
}
prim_priorityqueue