poj1679 kruskal

判断最小生成树是否唯一。kruskal时记录需要的边,然后枚举删除它们,每次删除时进行kruskal,如果值未变,表明不唯一。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
struct Node
{
int l;
int r;
int v;
}node[];
int pa[],n;
bool cmp(Node a,Node b)
{
return a.v<b.v;
}
void init()
{
for(int i=;i<=n;i++)
pa[i]=i;
}
int find(int x)
{
if(x!=pa[x])
pa[x]=find(pa[x]);
return pa[x];
}
int kruskal(Node temp)
{
init();
int i,j,ret=;
for(i=;i<n;i++)
{
int l1,l2;
if(node[i].l==temp.l&&node[i].r==temp.r)
continue;
l1=find(node[i].l);
l2=find(node[i].r);
if(l1!=l2)
{
ret+=node[i].v;
}
}
return ret;
}
int main()
{
int i,j,t,m;
scanf("%d",&t);
while(t--)
{
stack<Node>s;
scanf("%d%d",&n,&m);
init();
for(i=;i<m;i++)
{
scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].v);
}
sort(node,node+m,cmp);
int ret=;
for(i=;i<m;i++)
{
int l1,l2;
l1=find(node[i].l);
l2=find(node[i].r);
if(l1!=l2)
{
pa[l1]=l2;
ret+=node[i].v;
s.push(node[i]);
}
}
// printf("%d\n",ret);
int flag=;
while(!s.empty())
{
Node temp=s.top();
s.pop();
int ans=kruskal(temp);
if(ans==ret)
{
flag=;
break;
}
}
if(flag)
printf("%d\n",ret);
else printf("Not Unique!\n");
}
}
上一篇:喜大普奔!Django官方文档终于出中文版了


下一篇:gpg的使用