ACM资料大集合

				#include 
				#include 
				#include 
				#include 
				using namespace std;
				
				//kruscal 并查集
				/*
				输入：
				6 10
				1 2 6
				1 3 1
				1 4 5
				3 2 5
				3 4 5
				5 2 3
				5 3 6
				6 5 6
				6 3 4
				6 4 2
				
				输出：
				15
				*/
				#define NMAX 100
				typedef struct node
				{
					int fa;
					int rank;
				}node;
				
				typedef struct arc
				{
					int nd1;
					int nd2;
					int cost;
				}arc;
				
				node point[NMAX];
				arc shuru[NMAX];
				
				bool cmp(arc a,arc b)
				{
					return a.cost				}
				
				void init(int pnum)
				{
					int i;
					for(i=0;i					{
						point[i].fa=-1;
						point[i].rank=1;
					}
					sort(shuru+1,shuru+1+pnum,cmp);
				}
				
				int find(int x)
				{
					int root=x,tt;
					while(point[root].fa!=-1) root=point[root].fa;
					while(point[x].fa!=-1)
					{
						tt=point[x].fa;
						point[x].fa=root;
						x=tt;
					}
					return root;
				}
				
				bool join(int a,int b)
				{
					a=find(a);
					b=find(b);
					if(a!=b)
					{
						if(point[a].rank>point[b].rank) 
						{
							point[b].fa=a;
							point[a].rank+=point[b].rank;
						}
						else
						{
							point[a].fa=b;
							point[b].rank+=point[a].rank;
						}
						return true;
					}
					return false;
				}
				
				int solve(int pnum)
				{
					int i,ans=0,pa,pb;
					init(pnum);
					for(i=1;i					{
						if(join(shuru[i].nd1,shuru[i].nd2)==true)
							ans+=shuru[i].cost;
					}
					return ans;
				}
				int main()
				{
					int i,pnum,nnum;
					scanf("%d %d",&nnum,&pnum);
					for(i=1;i					{
						scanf("%d %d %d",&shuru[i].nd1,&shuru[i].nd2,&shuru[i].cost);
					}
					printf("%d\n",solve(pnum));
					return 0;
				}