POJ 1639 Picnic Planning （最小k度生成树）
#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<string>using namespace std; const int VM=30; // 点的数量const int EM=1010; // 边的数量const int INF=0x3f3f3f3f;int n,k; // n,结点个数int pre[VM]; // 父结点int father[VM]; // 生成树中的父结点bool edge[VM][VM]; // edg[i][j] = true 表示边[i,j]已在生成树中int best[VM]; // best[i]保存V0到i之间权值最大的边bool vis[VM]; // vis[i]表示点i是否以加入生成树bool mark[VM]; // 用于求连通分量最小生成树的标记int ans,w[VM][VM],dis[VM];map<string,int> mp;void DFS(int cur){ // 拉成有根树 for(int i=1;i<=n;i++) if(mark[i] && edge[i][cur]){ father[i]=cur; mark[i]=0; DFS(i); }}int BEST(int x,int v0){ // 记忆化搜索,求x到V0路径上权值最大的边 if(father[x]==v0) return -1; if(best[x]!=-1) return best[x]; int tmp=BEST(father[x],v0); if(tmp!=-1 && w[tmp][father[tmp]]>w[father[x]][x]) best[x]=tmp; else best[x]=x; return best[x];}int Prim(int s,int v0){ //求去掉与V0相连的边之后的连通分量的最小生成树 memset(mark,0,sizeof(mark)); vis[s]=mark[s]=true; for(int i=1;i<=n;i++){ dis[i]=w[s][i]; pre[i]=s; } int sum=0; for(int i=1;i<n;i++){ int u=-1; for(int j=1;j<=n;j++) if(!vis[j] && !mark[j]){ if(u==-1 || dis[j]<dis[u]) u=j; } if(u==-1) break; vis[u]=mark[u]=true; edge[pre[u]][u]=edge[u][pre[u]]=true; sum+=w[pre[u]][u]; for(int j=1;j<=n;j++) if(!vis[j] && !mark[j]){ if(dis[j]>w[u][j]){ dis[j]=w[u][j]; pre[j]=u; } } } int MIN=INF; int root=-1; // 树根 for(int i=1;i<=n;i++) if(mark[i] && w[i][v0]<MIN){ MIN=w[i][v0]; root=i; } mark[root]=0; // 拉成有根树,即把当前这个连通分量用一条到V0权值最小的边连接起来 DFS(root); // 并且构成一棵树,利用father数组保存父结点 father[root]=v0; return sum+MIN;}int minDegreeST(int v0,int k){ // v0是限制度的点， k是限制的度数 memset(father,-1,sizeof(father)); memset(vis,0,sizeof(vis)); memset(edge,0,sizeof(edge)); vis[v0]=true; int m=0; // 连通分支的个数 ans=0; // 所求答案 for(int i=1;i<=n;i++) // 步骤1: 先求出m限制树 if(!vis[i]){ m++; ans+=Prim(i,v0); } int minAdd,a,b,tmp; // 步骤2: 由m限制树得到m+1限制树 int change; // 回路上权值最大的边，用于交换 for(int i=m+1;i<=k && i<=n;i++){ memset(best,-1,sizeof(best)); for(int j=1;j<=n;j++) if(best[j]==-1 && father[j]!=v0) BEST(j,v0); minAdd=INF; for(int j=1;j<=n;j++) if(w[v0][j]!=INF && father[j]!=v0){ //遍历所有边 a=best[j]; b=father[best[j]]; tmp=w[v0][j]-w[a][b]; if(tmp<minAdd){ minAdd=tmp; change=j; } } if(minAdd>=0) //用于度数不大于k的限制，如果k限制，就不用break了 break; ans+=minAdd; a=best[change]; b=father[change]; w[a][b]=w[b][a]=INF; father[a]=b=v0; w[a][b]=w[b][a]=w[change][v0]; w[v0][change]=w[change][v0]=INF; } return ans;}int main(){ //freopen("input.txt","r",stdin); string str1,str2; while(~scanf("%d",&n)){ mp.clear(); for(int i=1;i<VM;i++) for(int j=1;j<VM;j++) w[i][j]=INF; int cw,cnt=1; mp["Park"]=1; for(int i=0;i<n;i++){ cin>>str1>>str2>>cw; if(mp[str1]==0) mp[str1]=++cnt; if(mp[str2]==0) mp[str2]=++cnt; if(w[mp[str1]][mp[str2]]>cw) //注意可能有重复边 w[mp[str1]][mp[str2]]=w[mp[str2]][mp[str1]]=cw; } n=cnt; scanf("%d",&k); printf("Total miles driven: %d\n",minDegreeST(1,k)); } return 0;}

?