| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:你给的数据没通过 还是ac了。。In Reply To:Re:给后来人一组数据 Posted by:20145104009 at 2015-07-19 21:02:40 #include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
int a,b,cost;
}c[10005];
int fa[105],tree[105][105],vis[10005],vis_tree[105];
int n,m,max1;
bool cmp(node x,node y)
{
if(x.cost<y.cost)
return true;
else
return false;
}
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void sec_tree(int a,int b)
{
vis_tree[a]=1;
if(a==b)
return ;
for(int i=1;i<=n;i++)
if(tree[a][i]&&!vis_tree[i])
{
if(max1<tree[a][i])
max1=tree[a][i];
sec_tree(i,b);
}
}
int main()
{
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
memset(vis,0,sizeof(vis));
memset(tree,0,sizeof(tree));
memset(&c,0,sizeof(&c));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=0;i<m;i++)
scanf("%d %d %d",&c[i].a,&c[i].b,&c[i].cost);
sort(c,c+m,cmp);
int sum=0;
for(int i=0;i<m;i++)
{
int x=find(c[i].a);
int y=find(c[i].b);
if(x!=y)
{
fa[x]=y,sum+=c[i].cost;
tree[x][y]=tree[y][x]=c[i].cost;
vis[i]=1;
}
}
int flag=0;
for(int i=0;i<m;i++)
{
if(!vis[i])
{
max1=-1;
memset(vis_tree,0,sizeof(vis_tree));
sec_tree(c[i].a,c[i].b);
if(max1==c[i].cost)
{
flag=1;
break;
}
}
}
if(!flag)
printf("%d\n",sum);
else
printf("Not Unique!\n");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator