Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:水题 1A 附代码

Posted by 70 at 2015-04-04 23:27:43 on Problem 1679
In Reply To:水题 1A 附代码 Posted by:bryant03 at 2015-02-14 15:25:25
> #include <cstdio>
> #include <cstdlib>
> #include <cstring>
> #define N 101
> using namespace std;
> int n,e,father[N];
> struct node {
> 	int u,v,c;
> 	node(){}
> 	node(int u,int v,double c):u(u),v(v),c(c){}
> }p[N*N];
> 
> void addnode(int u,int v,int c){
> 	p[e++]=node(u,v,c);
> } 
> 
> int cmp(const void *a,const void * b){
> 	node *aa=(node *)a;
> 	node *bb=(node *)b;
> 	return aa->c - bb->c; 
> }
> 
> int find(int x){
> 	if(x!=father[x])
> 		father[x]=find(father[x]);
> 	return father[x];
> }
> 
> void clear(){
> 	for(int i=0;i<=n;i++)
> 		father[i]=i;
> }
> 
> int kruskal(int n){
> 	clear();
> 	int m=0, ans=0;
> 	for(int i=0;i<e;i++){
> 		int u=find(p[i].u);
> 		int v=find(p[i].v);
> 		if(u==v) continue;
> 		for(int j=i+1;j<e;j++){
> 			if(p[j].c!=p[i].c) break;
> 			//printf("%d %d\n",)
> 			if(find(p[j].u)==u&&find(p[j].v)==v){
> 				//printf("sdya");
> 				return -1;
> 			}
> 		}
> 		m++;
> 		ans+=p[i].c;
> 		father[v]=u;
> 		if(m==n-1)
> 			break;
> 	}
> 	return ans;
> }
> 
> int main(){
> 	int t,l,a,b,c;
> 	scanf("%d",&t);
> 	while(t--){
> 		e=0;
> 		scanf("%d%d",&n,&l);
> 		for(int i=1;i<=l;i++){
> 			scanf("%d%d%d",&a,&b,&c);
> 			if(a<b) addnode(a,b,c);
> 			else addnode(b,a,c);
> 		}
> 		qsort(p,e,sizeof(p[1]),cmp);
> 		int ans=kruskal(n);
> 		if(ans==-1) printf("Not Unique!\n");
> 		else printf("%d\n",ans);
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator