POJ1679 The Unique MST - c++编程基础

题意：判断最小生成树是否唯一
思路：第一次用kruskal求出最小生成树，记为ans,然后依次去除已经选进来的边，进行kruskal，如果ans==kruskal()的话，则输出不唯一。
注意：1.第一次求kruskal时记得要先判断是否能生成最小生成树（但是我没判断就A了。。理论上来说是要判断的。。）
2.注意存放变的数组开大一点。我用G++交了几次一直WA，原代码改成C++交就RE，然后数组改了下大小就A了。被G++坑死了。
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define Max 20005
#define inf 1<<28
using namespace std;

struct kdq
{
int s,e,l;
} road[Max];
int f[Max];
bool visit[Max];
bool visit1[Max];
int n,m;

bool cmp(kdq x,kdq y )
{
return x.l }

int find(int x)
{
return f[x]==x x:f[x]=find(f[x]);
}

void Union(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)return ;
if(y>x)
f[y]=x;
else
f[x]=y;
}

int kruskal(int d)//d是用来删除边的
{
int num=0;
int num1=0;
for(int i=0; i {
if(i!=d)
{
int x=find(road[i].s);

int y=find(road[i].e);
if(y!=x)
{
num1++;
Union(x,y);
num+=road[i].l;
visit[i]=1;//记录第一次取来的边的标号
}
}
}
if(num1==n-1)//判断能生成最小生成树
return num;
else
return -1;
}

int main()
{
int i,j,k,l,T;
cin>>T;
while(T--)
{
memset(visit,0,sizeof(visit));
cin>>n>>m;
for(i=0; i<=n; i++)
f[i]=i;
for(i=0; i scanf("%d%d%d",&road[i].s,&road[i].e,&road[i].l);
sort(road,road+m,cmp);
int ans=kruskal(-1);
for(i=0; i visit1[i]=visit[i];//将第一标记的序号存入visit1[],因为visit[]在接下来的kruskal中还会改变
if(ans==-1)//这个判断不需要也可以过。。难道是数据水了？
{
cout<<0< continue;
}
bool flag=0;
for(i=0; i {
if(visit1[i])//如果是第一次取到的边
{
for(j=0; j<=n; j++)
f[j]=j;
if(kruskal(i)==ans)//如果删除了这条边后，最小生成树的值相等，则说明不唯一
{
flag=1;
break;
}
}
}
if(flag)
cout<<"Not Unique!"< else
cout< }
return 0;
}

作者：kdqzzxxcc