最小k限度生成树+poj（1639）代码

算法引入： 最小k度限制生成树,就是指有特殊的某一点的度不能超过k时的最小生成树; 如果T是G的一个生成树且dT(v0)=k,则称T为G的k度限制生成树; G中权值和最小的k度限制生成树称为G的最小k度生成树;   算法思想： 设特殊的那点为v0,先把v0删除,求出剩下连通图的所有最小生成树; 假如有m棵最小生成树,那么这些生成树必定要跟v0点相连; 也就是说这棵生成树的v0点至少是m度的; 若m>k,条件不成立,无法找到最小k度限制生成树; 若m<=k,则枚举m到k的所有最小生成树,即一步步将v0点的度加1,直到v0点的度为k为止; 则v0点度从m到k的(k-m+1)棵最小生成树中最小的那棵即为答案;   算法步骤： (1)先求出最小m度限制生成树: 原图中去掉和V0相连的所有边(可以先存两个图,建议一个邻接矩阵,一个邻接表,用方便枚举边的邻接表来构造新图); 得到m个连通分量,则这m个连通分量必须通过v0来连接; 则在图G的所有生成树中dT(v0)>=m; 则当k<m时,问题无解; 对每个连通分量求一次最小生成树; 对于每个连通分量V’,用一条与V0直接连接的最小的边把它与V0点连接起来,使其整体成为一个生成树; 就得到了一个m度限制生成树,即为最小m度限制生成树;   (2)由最小m度限制生成树得到最小m+1度限制生成树; 连接和V0相邻的点v,则可以知道一定会有一个环出现(因为原来是一个生成树); 只要找到这个环上的最大权边(不能与v0点直接相连)并删除,就可以得到一个m+1度限制生成树; 枚举所有和V0相邻点v,找到替换后,增加权值最小的一次替换(如果找不到这样的边,就说明已经求出); 就可以求得m+1度限制生成树; 如果每添加一条边,都需要对环上的边一一枚举,时间复杂度将比较高; 用动态规划解决; 设dp(v)为路径v0—v上与v0无关联且权值最大的边; 定义father(v)为v的父结点,由此可以得到状态转移方程: dp(v)=max(dp(father(v)),ω(father(v),v)); 边界条件为dp[v0]=-∞(因为每次寻找的是最大边,所以-∞不会被考虑),dp[v’]=-∞|(v0,v’)∈E(T);   (3)当dT(v0)=k时停止(即当V0的度为k的时候停止),但不一定k的时候最优;   算法实现： 并查集+kruskal; 首先,每个连通分量的的最小生成树可以直接用一个循环,循环着Kruskal求出; 这里利用了联通分量间的独立性,对每个连通分量分别求最小生成树,和放在一起求,毫不影响; 而且kruskral算法保证了各连通分量边的有序性; 找最小边的时候,可以用动态规划,也可以这么做： 先走一个循环,但我们需要逆过来加边,将与v0关联的所有边从小到达排序; 然后将各连通分量连接起来,利用并查集可以保证每个连通分量只有一条边与v0相连; 由于边已经从小到达排序,故与每个连通分量相连的边就是每个连通分量与v0相连中的最小边; 然后求m+1度的最小生成树时,可以直接用DFS,最小生成树要一直求到k度,然后从中找出一个最优值;  

poj1639经典题目啊 啊啊啊 啊啊 啊啊啊啊啊啊 啊啊啊啊

#include <iostream> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<vector> #include<cstdio> #include<map> using namespace std; const int maxn=100+5; const int inf=0x3f3f3f3f; struct node { int u,v,w,next; bool flag; bool operator<(const node &s)const { return w<s.w; } node(){flag=false;} }; node E[200000],E1[20000],E2[20000]; //E用来存储已经构成树的边； E1用来存题目中存在的边； E2与vo相连的边 int vcnt,cnt,ecnt,now,n,k,vo; //vcnt与vo相连的边数，cnt出现的地点数，ecnt树种以相连的边数，now是指最初的m（即初始建树与vo相连的边数） bool ok; map<string ,int >mp; int pr[maxn]; int head[maxn];// int findd(int x)//并查集 { if(x==pr[x]) return x; else return pr[x]=findd(pr[x]); } void swapp(int &a,int &b)//两个数交换，使u存的是vo { int t; if(b!=vo) return; else { t=a;a=b;b=t; } } void init(int u,int v,int w)//建边 { E[ecnt].u=u; E[ecnt].v=v; E[ecnt].w=w; E[ecnt].flag=true; E[ecnt].next=head[u];//节点位置，将边连入原先建好的图中 head[u]=ecnt++; } void go()//将m棵最小生成树与vo相连 { int u,v; int x,y; now=0; for(int i=0;i<vcnt;i++) { u=E2[i].u; v=E2[i].v; // cout<<u<<" "<<v<<endl; x=findd(u); y=findd(v); // cout<<x<<" "<<y<<endl; if(x != y) { pr[x]=y; E2[i].flag=true; init(u,v,E2[i].w); init(v,u,E2[i].w); now++;//一定别忘了此处计数 m } } } int vis[maxn]; int pre[maxn];//保存路径 //bfs好好理解！！！ int bfs(int s,int v,int ith,bool okk) //寻找当前图中s-v形成的环中的最大权值边（不与vo相连） { queue<int> q; while(q.size()) q.pop(); memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); vis[s]=1; q.push(s); while(q.size()) { int u=q.front();q.pop(); for(int i = head[u]; i != -1; i = E[i].next) { if(!E[i].flag)continue;//此边已经删去，不能考虑 int vv=E[i].v; if(!vis[vv]) { pre[vv]=i; vis[vv]=1; if(vv==v) break; q.push(vv); } } } int u=v; int id,res=0; while(1) { int i=pre[u]; //删掉环中与vo不关联的权值最大的边 if(E[i].u!=vo&&E[i].v!=vo&&res<E[i].w) { res=E[i].w; id=i; } u=E[i].u; if(u==s) break; } if(okk) { E[id].flag=E[id^1].flag=false;//删边^1的原因，E通常u和v互换成两个边，删的时候这两个应该都删掉 E2[ith].flag=true;//把与vo相连的边加入树中 init(s,v,E2[ith].w); init(v,s,E2[ith].w); } return E2[ith].w-res; //判断所求最大权值与当前vo边权大小关系（为负才删边加边） } void ff() { int id=-1,res =inf;//id-1 int u,v,w; //寻找最合适可加边 for(int i = 0; i < vcnt; i++) { u=E2[i].u; v=E2[i].v; w=E2[i].w; if(!E2[i].flag) { int tmp=bfs(vo,v,i,false);//此边的 if(tmp<res) { res=tmp; id=i; } } } if(res>=0)//说明已经再也没有更大的值 { ok=false;//剪枝 return; } bfs(vo,E2[id].v,id,true);//res<0 可以加边删边 } int get_ans() { int ans=0; for(int i=0;i<ecnt;i+=2) { if(E[i].flag)//此处不可少 ans+=E[i].w; } return ans; } void solve() { int u,v,w; memset(head,-1,sizeof(head)); sort(E1,E1+n); ecnt=0;vcnt=0; for(int i=0 ; i <= cnt ; i++) pr[i]=i; for(int i = 0;i < n ; i++) { u=E1[i].u; v=E1[i].v; w=E1[i].w; swapp(u,v); if(u == vo || v == vo )//将vo边单独存储 { E2[vcnt].u=u; E2[vcnt].v=v; //cout<<E2[vcnt].v<<endl; E2[vcnt].w=w; E2[vcnt].flag=false; vcnt++; continue;//注意！ } int x,y; x=findd(u); y=findd(v); if(x != y) //建多个最小生成树（抠掉vo的） { pr[x]=y; init(u,v,w); init(v,u,w); } } go();//用vo将这多个最小生成树相连 ok=true; for(int i=now;i<k&&ok;i++)//由m到m+1的进化 ff(); int ans=get_ans();//计算权值 printf("Total miles driven: %d\n",ans); } int main() { cin>>n; string a,b; int ww; cnt=0; mp.clear(); for(int i = 0;i < n ;i ++) { cin>>a>>b>>ww; if (!mp[a]) mp[a] = ++cnt;//cnt++就错了。。。很奇怪 if (!mp[b]) mp[b] = ++cnt; E1[i].u = mp[a]; E1[i].v = mp[b]; E1[i].w = ww; } cin>>k; string c = "Park"; vo = mp[c]; solve(); return 0; } 累死我了。。。。

来源点击打开链接ll思路清晰，可惜他给的代码是错的，不过算法是引用的他的

代码点击打开链接