最小度生成树

#include <iostream>
#include <string>
using namespace std;
int m,n,ma,mai,p,k,q,zu,u,v,en,tol,ztree=0,maxx=100000003;
string s,t;
bool g[30][30]={0},ff[30];
int a[30][30];
bool b[30][30],vi[30],sf[30];
string ss[30];
int hd[30],fu[30],belong[30],cun1[30],cun2[30],zuida[30],zuii[30];
//zuida保存vi到v0路径上不与v0相连的权值最大的边，zuii表示这条边对应的点，这条边还有另外一个点就是fu[i]了
void prim(int v){           //prim最小生成树，同时找出联通量
 int i,j,min,go;
 int ans=0;
 for (i=0;i<n;i++){
  fu[i]=v;
  hd[i]=a[v][i];
 }
 hd[v]=0;
 ff[v]=true;
 hd[en]=0;
 for (i=1;i<n;i++){
  min=maxx;
  for (j=0;j<n;j++)
   if(hd[j]>0&amp;&amp;hd[j]<min){
    v=j;
    min=hd[j];
   }
  if (min==maxx) break;
  b[(fu[v])][v]=1;
  b[v][(fu[v])]=1;
  hd[v]=0;
  belong[v]=zu;
  ff[v]=true;
  ztree+=a[fu[v]][v];
  for (j=0;j<n;j++)
   if(a[v][j]<hd[j]){
    fu[j]=v;
    hd[j]=a[v][j];
   }
 }
}

void dfs(int v){           //深度搜索，找出每一次各个节点到park节点的最大的边
     int i;
     vi[v]=true;
     if (v==en||fu[v]==en){
         zuida[v]=0;
         zuii[v]=v;
   sf[v]=false;
         }
     else {
     zuida[v]=zuida[(fu[v])];
     zuii[v]=zuii[(fu[v])];
     if (zuida[v]<a[fu[v]][v]){
         zuida[v]=a[fu[v]][v];
         zuii[v]=v;
         }
     } 
     for (i=0;i<n;i++)
        if (b[v][i]&amp;&amp;!vi[i]){
            fu[i]=v;
            dfs(i);
        }
}

int main(){
 int i,j;
 bool find;
 cin>>m;
 n=0;
  for (i=0;i<21;i++)
  for (j=0;j<21;j++) {
   a[i][j]=maxx;
   b[i][j]=0;
  }
 for (i=0;i<m;i++){
  cin>>s>>t>>k;
  find=false;
  for (j=0;j<n;j++){
   if (ss[j]==s){ u=j;
   find=true;}
  }
  if (find==false) {
   ss[n]=s;
   u=n;
   if (s==&quot;Park&quot;) en=n;
   n++;
  }
  find=false;
  for (j=0;j<n;j++){
   if (ss[j]==t){ v=j;
   find=true;}
  }
  if (find==false) {
   ss[n]=t;
   v=n;
   if (t==&quot;Park&quot;) en=n;
   n++;
  }
  a[u][v]=k;
  a[v][u]=k;
  g[u][v]=true;
  g[v][u]=true;
 }
 cin>>tol;
 for (i=0;i<n;i++){
  ff[i]=false;
  cun1[i]=maxx;
  cun2[i]=maxx;
  zuida[i]=maxx;
  zuii[i]=maxx;
  vi[i]=false;
  sf[i]=true;
 }
 ff[en]=true;
 zu=1;
 for (i=0;i<n;i++)
  if (!ff[i]) {
   belong[i]=zu;
   prim(i);
   zu++;
  }
 for (i=0;i<n;i++){
  if (a[i][en]!=maxx&amp;&amp;cun1[belong[i]]>a[i][en]){
   cun1[belong[i]]=a[i][en];
   cun2[belong[i]]=i;
  }
    }
 for (i=1;i<zu;i++){
  b[cun2[i]][en]=1;
  b[en][cun2[i]]=1;
  ztree+=a[en][cun2[i]];
 }
 dfs(en);
 for (k=zu;k<=tol;k++){     //最小度的核心代码
  ma=maxx;
  for (i=0;i<n;i++)
   if (g[en][i]&amp;&amp;!b[en][i]&amp;&amp;sf[i]&amp;&amp;(a[en][i]-zuida[i]<ma)){
    ma=a[en][i]-zuida[i];
    mai=i;
   }
  if (ma>=0) break;
     b[mai][en]=1;
  b[en][mai]=1;
  u=zuii[mai];
  v=fu[u];
  b[u][v]=0;
  b[v][u]=0;
  fu[mai]=en;
  sf[mai]=false;
  ztree+=ma;
  dfs(mai);
 }
 cout<<&quot;Total miles driven: &quot;<<ztree<<endl;
 system(&quot;pause&quot;);
 return 0;
}