#include <iostream.h>
#include <math.h>
const int N=10; 
float s[2][N]={{0,1,2,1,3,6,5,8,10,12},
{0,0,1,2,1,4,5,9,9,10}};
float D[N][N],DT[N][N],LDT[N][N];
float temp;
int i,j,k;

void minispantree_prim(float gn[N][N],float DT[N][N],float bl[N][N],int u0)
 /* 從u0出發(fā)構(gòu)造網(wǎng)gn的最小生成樹，按普里姆算法輸出生成樹上各條邊 */
{
	struct node  {  int vex;
                  float lowcost;
               } closedge[N];
  for(i=0;i<N;i++)
	  for (j=0;j<N;j++)
		  bl[i][j]=90;
   for (int v=1;v<N;v++)
    {closedge[v].vex=u0;
     closedge[v].lowcost=gn[u0][v];
   };
  closedge[u0].lowcost=0;    // 輔助數(shù)組初始化
for ( i=0;i<N-1;i++ )  // 只需N-1條邊 
  {// k = minimun(closedge);
   k=1;
   float val=999;
   for(int v=1;v<N;v++)
   if (closedge[v].lowcost>0 && closedge[v].lowcost<val)
   { k=v; val=closedge[v].lowcost;}     
//求minimum函數(shù)求得K值,使closedge[k].lowcost=MIN{closedge[v].lowcost}
//closedge[v].lowcost>0,v V-U}, 函數(shù)minimun()求得k值,達(dá)到某種極小 
     DT[closedge[k].vex][k]=DT[k][closedge[k].vex]=val; 
	 bl[closedge[k].vex][k]=bl[k][closedge[k].vex]=1;
   /*  記錄生成樹的邊  */
     closedge[k].lowcost=0;   /*  頂點(diǎn)k并入U(xiǎn)集  */
     for (v=0;v<N; v++)
        if ( (closedge[v].lowcost>0)&&(gn[k][v]<closedge[v].lowcost))
                 { closedge[v].lowcost=gn[k][v];closedge[v].vex=k;}
        /*  在新的頂點(diǎn)并集合以后，重新選擇具有最小代價(jià)的邊  */
   }      
 }    
void floyd(float a[N][N],float c[N][N],int path[N][N])
//c 為鄰接矩陣
{int i,j,k;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++) /*初始化*/
   {a[i][j]=c[i][j]; /*置a數(shù)組 */
    path[i][j]=j; /*path全初始化為0 */
   }
 for(i=0; i<N;i++)
     a[i][i]=0; /*主對角線置0，頂點(diǎn)自己到自己的長度為0*/
 for(k=0;k<N;k++)
    for(i=0;i<N;i++)
      for(j=0;j<N;j++)
        if (a[i][k]+a[k][j]<a[i][j])
          { a[i][j]=a[i][k]+a[k][j];
            path[i][j]=path[i][k]; 
			//i的直接后繼為k
          }
}
void main(void)
{ int k=0;
  int h=0;
  float tp=0;
  float LDT[N][N];
  float LTDT[N][N];
float LLTDT[N][N];
  int Lpath[N];
  float boola[N][N];
  float b[N][N];
  float TREE90[N][N];
  int pp[N][N];
  int ppp;
  int width[N];
  int l=0;
  int next; 
  int p[N][N];
  cout<<"first\n";
  for (i=0;i<N;i++)
   for(j=1;j<N;j++)
   {float ft=(float)sqrt((s[0][i]-s[0][j])*(s[0][i]-s[0][j])+(s[1][i]-s[1][j])*(s[1][i]-s[1][j]));
    D[i][j]=ft;D[j][i]=ft;   
	}//qiuchu adjacent matrix
   cout<<"D: \n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
	   cout<<D[i][j]<<"  ";
     cout<<"\n";
   }
   minispantree_prim(D,DT,boola,0);
   //求出最小生成樹并存入DT[N][N]，邏輯樹boola[N][N],非樹枝存90
   cout<<"最小生成樹DT:\n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
	   cout<<DT[i][j]<<"  ";
    cout<<"\n";
   }
   cout<<"boola:\n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
     cout<<boola[i][j]<<"  ";
    cout<<"\n";
   }
   for(i=0;i<N;i++)
     for(j=0;j<N;j++)
	  TREE90[i][j]=boola[i][j];
      
  for(i=0;i<N;i++)
   for(j=0;j<N;j++)
	   LTDT[i][j]=LDT[i][j]=DT[i][j]; //LTDT作臨時(shí)保存用
cout<<"最小生成樹LDT=DT \n";
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
      cout<<LDT[i][j]<<"  ";
    cout<<"\n";
   }
    
  for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LDT[i][j]>tp){tp=LDT[i][j];k=i;h=j;}
  cout<<tp<<" maxpoint no useful "<<(k+1)<<" "<<(h+1)<<" \n";
  cout<<"準(zhǔn)備求任意兩點(diǎn)間的最小距離,LTDT轉(zhuǎn)化為邏輯樹，點(diǎn)間無邊時(shí)置90 :\n";  
  
  /*for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LTDT[i][j]>0) LTDT[i][j]=1;else LTDT[i][j]=90;
   
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
     cout<<LTDT[i][j]<<"  ";
    cout<<"\n";
   }*/
   //求出任意兩點(diǎn)間的最短距離存入矩陣LLTDT[N][N]
   floyd(LLTDT,boola,p);//
	cout<<"求生成樹中任意兩點(diǎn)間的最小距離放入LLTDT:\n";
	for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LLTDT[i][j]>90) LLTDT[i][j]=0;
   for (i=0;i<N;i++)
   {for(j=0;j<N;j++)
      cout<<LLTDT[i][j]<<"  ";
    cout<<"\n";
   }
   //掃描LLTDT中最大邊所在位置（k，h）,Lpath[N]存放其路徑，即最大直徑
   tp=0;
	k=0; 
	h=0;
	for (i=0;i<N;i++)
     for(j=0;j<N;j++)
       if(LLTDT[i][j]>tp){tp=LLTDT[i][j];k=i;h=j;}
      //找出最長的路徑，即直徑（樹中的）
	cout<<"\n輸出直徑長及其上的各點(diǎn):\n";
	cout<<"直徑長:"<<tp<<" 兩個(gè)端點(diǎn): "<<(k+1)<<"和 "<<(h+1)<<" \n";
Lpath[0]=k;
	 l=0;
	 next=p[k][h];     /* next為起點(diǎn)的直接后繼 */
     if (next==0) cout<<"no path\n";
	 else
	 {while (next!=h)
		{l++;Lpath[l]=next;
         next=p[next][h];  /* 繼續(xù)找下一個(gè)直接后繼 */
		}
	   l++;Lpath[l]=h;}
	 cout<<"\n直徑上的各點(diǎn):\n";
	 for(i=0;i<=l;i++) cout<<Lpath[i]<<" ";
     cout<<"\n";
// 將直徑中的點(diǎn)存入Lpath
//再求出直徑上每一點(diǎn)的寬度
  cout<<"boola:\n";
  for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<boola[i][j]<<" ";
    cout<<"\n";
  } 
  cout<<"ooooo\n";
  //boola[][]中存放的是樹支和其他大的值，把樹上直徑中點(diǎn)間距離置為90，
  //即不希望直徑上的邊參與計(jì)算最小距離
cout<<"\n";
for(i=0;i<=l;i++)
   for(j=0;j<=l;j++)
	  LTDT[Lpath[i]][Lpath[j]]=boola[Lpath[i]][Lpath[j]]=90;
    
cout<<"\n顯示pppppp boola:+90\n";
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<boola[i][j]<<" ";
    cout<<"\n";
  }
cout<<"llll\n";
floyd(b,boola,pp);
cout<<"b為不含直徑上的點(diǎn)間距離的任意兩點(diǎn)間的最小長度:\n";
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<b[i][j]<<" ";
    cout<<"\n";
  }
//再求出不包括最長直徑在內(nèi)，生成樹上任意兩點(diǎn)的最小距離。
//距離大的(999)的邊不計(jì)算在內(nèi)?
for(i=0;i<N;i++)
  for(j=0;j<N;j++)
	  if(b[i][j]>=90) b[i][j]=0;
cout<<"輸出b-90,是去掉最大值后，不含直徑上點(diǎn)之間的最小長度:\n";   
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<b[i][j]<<" ";
    cout<<"\n";
  }
cout<<"hhhhyhyh\n";
cout<<"直徑上每點(diǎn)的寬度???:b中存放的是不含直徑在內(nèi)的任意兩點(diǎn)間的最小距離\n";
for (j=0;j<l;j++)
{  int tmp=0;
   for(i=0;i<N;i++)
     if (b[Lpath[j]][i]>tmp)tmp=(int)b[Lpath[j]][i];
   width[j]=(int)tmp;
}
cout<<"\n直徑上每個(gè)點(diǎn):\n";
for (j=0;j<l;j++)
  cout<<Lpath[j]<<" ";
cout<<"\n直徑上每點(diǎn)的寬度:\n";
for (j=0;j<l;j++)
  cout<<width[j]<<" ";
cout<<"\n";
  //由k到h,對直徑上的每點(diǎn)掃描，求出局部最小，并加以分?jǐn)?//ppp=width[0];
i=1;
while (i<=l) 
{//ppp=width[Lpath[i]];
	if	((width[Lpath[i-1]]-width[Lpath[i]])>=1) break;
 else i++;
}
cout<<"TREE90-斷點(diǎn)\n";
TREE90[Lpath[i-1]][Lpath[i]]=TREE90[Lpath[i]][Lpath[i-1]]=90;
k=i;
h=i+1;
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<TREE90[i][j]<<" ";
    cout<<"\n";
  }
cout<<"兩斷點(diǎn)"<<k+1<<"---"<<h+1<<"\n";
int pa[N][N];
float dd[N][N];
floyd(dd,TREE90,pa);//重新求樹上任意兩點(diǎn)之間的距離
cout<<"dd: \n";
for(i=0;i<N;i++)
  { for(j=0;j<N;j++)
	  cout<<dd[i][j]<<" ";
    cout<<"\n";
  }  

cout<<"first center "<<k+1<<":";//第一個(gè)中心k+1,所有與k+1相通的點(diǎn)為一類，
for (j=0;j<N;j++)
  if (dd[j][k]<90) cout<<j+1<<" ";
cout<<"\n";
cout<<"second center "<<h+1<<":";//第二個(gè)中心
for (j=0;j<N;j++)
  if (dd[j][h]<90)cout<<j+1<<" ";
//所有與h+1相通的點(diǎn)屬于另一類（在樹上）。
   cout<<"\n";
}