| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 24034 | Accepted: 8535 |
Description
Input
Output
Sample Input
2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2
Sample Output
3 Not Unique!
今天看了一天的次小生成树，还是有几个细节不是太理解，今晚再跟舍友探讨一下
题意：判断是不是有唯一的最小生成树（即连接所有点的边的权值之和是最小且唯一的）如果是则输出最小生成树（mst）的权值，否则输出 Not Unique！
题解：先利用prime算法求出最小生成树，在prime求MST的过程中 用数组存储MST里面任意两点间的唯一的路中 权值最大的那条边的权值。
最后枚举不在MST里面的边<i,，j>，判断<i，j>的权值 是否 和 MST里面 i 到 j 的最大权值相等，只要有一条边满足就可以说明MST不唯一。
（因为我们可以用这条不在MST的边来 代替 在MST的边，这样MST肯定不唯一）
MST更新：MST[ next ][ j ] = max(MST[ set[ next ] ][ j ], low[ next ])。（ j 属于MST里面的点）
#include<stdio.h>
#include<string.h>
#define MAX 110
#define max(x,y)(x>y?x:y)
#define INF 0x3f3f3f3f
int map[MAX][MAX],vis[MAX],set[MAX];
int low[MAX];
int mst[MAX][MAX];//记录 mst中i到j的最大权值
int inmst[MAX][MAX];//判断边是否在mst中
int n,m;
void init()//初始化
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
if(i==j)
map[i][j]=0;
else
map[i][j]=INF;
}
}
}
void getmap()//建图
{
int i,a,b,c;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]>c)
map[a][b]=map[b][a]=c;
}
}
void prim()
{
int i,j,min,mindis=0,next;
memset(mst,0,sizeof(mst));
memset(inmst,0,sizeof(inmst));
for(i=1;i<=n;i++)
{
low[i]=map[1][i];
vis[i]=0;
set[i]=1;//所有点的前驱都是起点
}
vis[1]=1;
for(i=1;i<n;i++)
{
min=INF;
for(j=1;j<=n;j++)
{
if(!vis[j]&&min>low[j])
{
min=low[j];
next=j;
}
}
mindis+=min;
vis[next]=1;
int fa=set[next];//求出当前新起点的前驱
inmst[fa][next]=inmst[next][fa]=1;
for(j=1;j<=n;j++)
{
if(vis[j]&&j!=next)
mst[j][next]=mst[next][j]=max(mst[fa][j],low[next]);
if(!vis[j]&&low[j]>map[next][j])
{
low[j]=map[next][j];
set[j]=next;//以新起点为所有点的新前驱
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(map[i][j]!=INF&&!inmst[i][j])//不在最小生成树中且存在的边
{
if(map[i][j]==mst[i][j])//代表可以有边替代最小生成树中的边（最小生成树不唯一）
{
printf("Not Unique!\n");
return ;
}
}
}
}
printf("%d\n",mindis);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
getmap();
prim();
}
return 0;
}
poj 1679 The Unique MST【次小生成树】
原文：http://www.cnblogs.com/tonghao/p/4725341.html