学步园

这是一个 最小k度限制生成树 的题，看了国家集训队2004汪汀的论文，感觉他没有写彻底，求出最小m度限制生成树，扩展到m+1后，best数组应该要跟新，然后才能去扩展m+2，依次类推，直到度数为k。

sign[]：记录已和v0相连得节点。

best[]：记录v---v0路径上与v0无关联且权值最大的边，利用动态规划求得，且要跟新。

#include<iostream><br /> #include<cstdlib><br /> #include<cstring><br /> using namespace std;<br /> #define N 25<br /> #define max_int 99999999<br /> int sign[N],cost[N][N],dist[N],s[N],pi[N],best[N];<br /> int weight;<br /> char nam[N][15];<br /> struct Edge<br /> {<br /> char a[15],b[15];<br /> int dist;<br /> };<br /> Edge e[N*N];<br /> char temp[N*N][15];<br /> int choose(int n)<br /> {<br /> int m=max_int,pos=-1;<br /> for(int i=1;i<=n;i++)<br /> if(dist[i]<m&&!s[i])<br /> {<br /> m=dist[i];<br /> pos=i;<br /> }<br /> return pos;<br /> }<br /> int mymax(int a,int b)<br /> {<br /> if(a>b)<br /> return a;<br /> else<br /> return b;<br /> }<br /> void prim(int v,int v0,int n)//每个连通分量的最小生成树<br /> {<br /> int u,i;<br /> dist[v]=cost[v][v0];<br /> pi[v]=v0;<br /> while(1)<br /> {<br /> u=choose(n);<br /> if(u==-1)<br /> break;<br /> if(pi[u]!=v0)<br /> best[u]=mymax(best[pi[u]],cost[pi[u]][u]);//动态规划求得best<br /> s[u]=1;<br /> weight+=dist[u];<br /> for(i=1;i<=n;i++)<br /> if(!s[i]&&dist[i]>cost[u][i])<br /> {<br /> pi[i]=u;<br /> dist[i]=cost[u][i];<br /> }<br /> }<br /> }<br /> void aprim(int n,int v0)//m度扩展到m+1度后，对best进行更新<br /> { //方法就是再求一次最小生成树，每次v0是m+1度，m+2度....k度<br /> int u,i;<br /> while(1)<br /> {<br /> u=choose(n);<br /> if(u==-1)<br /> break;<br /> if(pi[u]!=v0)<br /> best[u]=mymax(best[pi[u]],cost[u][pi[u]]);<br /> s[u]=1;<br /> for(i=1;i<=n;i++)<br /> if(!s[i]&&i!=v0&&dist[i]>cost[u][i])<br /> {<br /> pi[i]=u;<br /> dist[i]=cost[u][i];<br /> }<br /> }<br /> }<br /> void deg_prim(int v0,int k,int n)<br /> {<br /> int i,j,t=0,degmst,m,pos,r,c,h;<br /> for(i=1;i<=n;i++)<br /> if(cost[v0][i]<max_int)<br /> best[i]=-max_int;<br /> memset(sign,0,sizeof(sign));<br /> for(i=1;i<=n;i++)<br /> dist[i]=max_int;<br /> best[v0]=-max_int;<br /> pi[v0]=v0;<br /> s[v0]=1;<br /> for(h=1;h<=n;h++)//求m个连通分量的最小生成树<br /> for(i=1;i<=n;i++)<br /> if(cost[v0][i]<max_int&&!s[i])<br /> {<br /> m=cost[v0][i];<br /> pos=i;<br /> for(j=1;j<=n;j++)<br /> if(cost[v0][j]<m&&!s[j])<br /> {<br /> m=cost[v0][j];<br /> pos=j;<br /> }<br /> prim(pos,v0,n);<br /> sign[pos]=1;<br /> t++;<br /> }<br /> degmst=weight;//weight保存了最小m度生成树的权值<br /> for(j=1;j<=k-t;j++)//直到k度为止<br /> {<br /> m=max_int;<br /> for(i=1;i<=n;i++)<br /> if(cost[v0][i]<max_int&&!sign[i])<br /> {<br /> if(m>degmst+cost[v0][i]-best[i])<br /> {<br /> m=degmst+cost[v0][i]-best[i];<br /> pos=i;<br /> }<br /> }<br /> degmst=m;<br /> if(degmst<weight)<br /> weight=degmst;<br /> sign[pos]=1; //为best更新初始化必要的数据<br /> pi[pos]=v0;<br /> best[pos]=-max_int;<br /> for(i=1;i<=n;i++)<br /> {<br /> if(i!=v0)<br /> {<br /> s[i]=0;<br /> if(sign[i])<br /> dist[i]=0;<br /> else<br /> dist[i]=max_int;<br /> }<br /> }<br /> aprim(n,v0);<br /> }<br /> }<br /> int cmp(const void *a,const void *b)<br /> {<br /> return strcmp((char*)a,(char *)b);<br /> }<br /> int mysearch(char source[][15],char key[],int n)<br /> {<br /> int mid,left=1,right=n;<br /> while(left<=right)<br /> {<br /> mid=(left+right)/2;<br /> if(strcmp(key,source[mid])==0)<br /> return mid;<br /> else if(strcmp(key,source[mid])>0)<br /> left=mid+1;<br /> else<br /> right=mid-1;<br /> }<br /> }<br /> int main()<br /> {<br /> int n,i,h=0,k=1,j,a,b,c;<br /> scanf("%d",&n);<br /> for(i=1;i<=n;i++)<br /> {<br /> scanf("%s%s%d",e[i].a,e[i].b,&e[i].dist);<br /> strcpy(temp[h],e[i].a);<br /> strcpy(temp[h+1],e[i].b);<br /> h+=2;<br /> }<br /> qsort(temp,h,sizeof(temp[0]),cmp);<br /> strcpy(nam[1],temp[0]);<br /> for(i=1;i<h;i++)<br /> if(strcmp(temp[i],temp[i-1]))<br /> strcpy(nam[++k],temp[i]);<br /> for(i=1;i<=k;i++)<br /> for(j=i;j<=k;j++)<br /> cost[i][j]=cost[j][i]=max_int;<br /> for(i=1;i<=n;i++)<br /> {<br /> a=mysearch(nam,e[i].a,k);<br /> b=mysearch(nam,e[i].b,k);<br /> if(e[i].dist<cost[a][b])<br /> cost[a][b]=cost[b][a]=e[i].dist;<br /> }<br /> scanf("%d",&c);<br /> weight=0;<br /> deg_prim(mysearch(nam,"Park",k),c,k);<br /> printf("Total miles driven: %d/n",weight);<br /> return 0;<br /> }