首页 > 代码库 > poj1639 Picnic Planning 最小度数限制生成树
poj1639 Picnic Planning 最小度数限制生成树
题意:若干个人开车要去park聚会,但是park能停的车是有限的,为k。所以这些人要通过先开车到其他人家中,停车,然后拼车去聚会。另外,车的容量是无限的,他们家停车位也是无限的。求开车总行程最短。
就是求一最小生成树,但是对于其中一个点其度不能超过k。
思路:
1. 将park点取出 将剩下的点求出最小生成树 出现i个联通块
2. 再每个块中选择与park点相邻的最小边
到此park点已经连了i条边
park点最大可以连接k个点
得到Sum值
3. 需要求出i+1-->k 条的Sum值
每次添加一条边在树上形成一个环 然后 删去一条环上的边(权值最大)取Sum=min(Sum,Sum+添加边-删去边) 复杂度O(n^2)
因为第三步复杂度高需要优化第三步
优化:先记录Vi->Vp路径上且不与Vp直接相连的边的权值的Max[ i ]
添加边时 取cost(Vi,Vp)-Max [ i ]最小值 添加(Vi,Vp)边
再枚举ViVp原有的路径上不与Vp相连的边,找到最大权值的边;
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; const int maxn =111+5; const int maxe = 15000+5; const int INF = 460002326; #include <map> map<string,int>mp; map<string,int>::iterator it; int car,n,cost[maxn][maxn],sum,father[maxn]; int best[maxn]; bool vis[maxn]; bool edge[maxn][maxn]; bool use[maxn]; void dfs(int root)//将一个连通块中各个点标记其father { for(int i=1; i<n; i++) { if(vis[i]&&edge[root][i]) { father[i]=root; vis[i]=false; dfs(i); } } } void prim(int s) { int Min_i,Min,dis[maxn],num[maxn]; memset(vis,false,sizeof(vis)); for(int i=0; i<n; i++) { dis[i]=cost[i][s]; num[i]=s;//此时dis[i]的值来自哪个点 } dis[s]=0; vis[s]=use[s]=true; while(true) { Min=INF,Min_i=-1; for(int i=0; i<n; i++) { if(!use[i]&&!vis[i]&&(Min_i==-1||Min>dis[i])) { Min_i=i; Min=dis[i]; } } if(Min==INF) break; sum+=Min; vis[Min_i]=true; use[Min_i]=true;//标记连通块用过的点 edge[Min_i][num[Min_i]]=edge[num[Min_i]][Min_i]=true; for(int i=0; i<n; i++) { if(!use[i]&&!vis[i]&&dis[i]>cost[i][Min_i]) { num[i]=Min_i; dis[i]=cost[i][Min_i]; } } } Min=INF; int root=-1; for(int i=0; i<n; i++)//寻找该连通块到Park点的最小距离 { if(vis[i]&&cost[0][i]<Min&&i!=0)//在这棵树中 { Min=cost[0][i]; root=i; } } vis[root]=false; dfs(root);//以root为根 father[root]=0; sum+=Min; } int Best(int j)//更新其中各个点到park路径上边权值最大的点 { if(father[j]==0)//如果father为0,记为-1 return best[j]=-1; if(best[j]!=-1) return best[j];//如果已经存在 ,直接返回 int tmp=Best(father[j]); if(tmp!=-1)//这说明其父节点不与park相连 { if(cost[tmp][father[tmp]]>cost[father[j]][j]) best[j]=tmp; else best[j]=j; } else best[j]=j;//其父节点与source相连 将j赋给自己 return best[j]; } void solve() { int mst=0; memset(father,-1,sizeof(father)); memset(use,0,sizeof(use)); memset(edge,false,sizeof(edge)); use[0]=true; for(int i=0; i<n; i++) { if(!use[i])//use用过要标记 { prim(i);//除Park外建最小生成树 mst++; } } for(int i=mst+1; i<n&&i<=car; i++) { memset(best,-1,sizeof(best)); for(int j=0; j<n; j++) { if(j!=0&&best[j]==-1&&father[j]!=0) Best(j); } int minadd=INF; int ax,bx,change; for(int j=0; j<n; j++) { if(cost[0][j]!=INF&&father[j]!=0) { ax=best[j]; bx=father[ax]; if(minadd>cost[0][j]-cost[ax][bx])//cost[0][j]表示添加的边 cost[ax][bx]表示断开的边 { minadd=cost[0][j]-cost[ax][bx];//更新减小的值以及连接的点 change=j; } } } if(minadd>=0) //表示要增加sum值 则已经得到最小的sum值 break; sum+=minadd;//更新 ax=best[change]; bx=father[ax]; cost[ax][bx]=cost[bx][ax]=INF; father[change]=0; cost[0][change]=cost[change][0]=INF; } } int main() { int t; // freopen("in.txt","r",stdin); cin>>t; mp.clear(); string s1,s2; int val; for(int i=0; i<maxn; i++) for(int j=0; j<maxn; j++) cost[i][j]=INF; n=1,sum=0; mp["Park"]=0;//Park为0; for(int i=0; i<t; i++) { cin>>s1>>s2>>val; it=mp.find(s1);//map映射值 if(it==mp.end()) mp[s1]=n++; it=mp.find(s2); if(it==mp.end()) mp[s2]=n++; if(cost[mp[s1]][mp[s2]]>val)//可能会有重边。事实上没有。。。。。 cost[mp[s1]][mp[s2]]=cost[mp[s2]][mp[s1]]=val; } cin>>car; solve(); cout<<"Total miles driven: "<<sum<<endl; return 0; }
poj1639 Picnic Planning 最小度数限制生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。