#include <iostream>
#ifndef SetMaxVertices
#define SetMaxVertices
const int MaxNumVertices=10;
#endif

#ifndef MAXINT
#define MAXINT 32767		// 機器可表示的, 問題中不可能出現的大數
#endif


using std::ostream;
using std::endl;

class MinSpanTree;			//最小生成樹的前視類聲明99

class MSTEdgeNode
{			//最小生成樹邊結點的類聲明
public:
	friend class MinSpanTree;
	friend ostream& operator <<(ostream& strm, MSTEdgeNode e);
    int tail, head;				//兩頂點位置
    int key;					//邊上的權值
};

class MinSpanTree {				//最小生成樹的類定義
private:
   MSTEdgeNode *edgeValue;			//用邊值數組表示樹
   int MaxSize, n,cost;				//數組的最大元素個數和當前個數
public:
   MinSpanTree ( int sz = MaxNumVertices-1 ) : MaxSize (sz), n (0),cost(0) 
   {
		#ifdef DEBUG
		cout << "MinSpanTree Construct !" << endl;
		#endif
		edgeValue = new MSTEdgeNode[MaxSize]; 
   }
   ~MinSpanTree(){delete[] edgeValue;}
   void addEdge(int ,int ,int );
   friend ostream& operator <<(ostream& strm, MinSpanTree t);
};
void MinSpanTree::addEdge(int tail,int head,int 
dist)//向生成樹邊值數組內存放
{
	   edgeValue[n].tail = tail;
	   edgeValue[n].head = head;
	   edgeValue[n].key = dist;
	   cost=cost+dist;
	   n++;
}
ostream& operator <<(ostream& strm, MSTEdgeNode e)
{
	strm<<"("<<e.tail<<","<<e.head<<")";
	return strm;
}
ostream& operator <<(ostream& strm, MinSpanTree t)
{
	for (int i=0;i<t.n;i++)
		strm<<t.edgeValue[i];
	strm<<endl;
	strm<<"Total Cost="<<t.cost<<endl;
	return strm;
}