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