本文主要是介绍POJ 1639 有度限制的最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路有点长。。见论文。。非常清晰。。尤其是PPT
1.PPT
http://wenku.baidu.com/view/70ef0e00eff9aef8941e06db.html
2.IOI2004国家集训队论文--王汀《最小生成树问题的扩展》
http://wenku.baidu.com/view/41800d66ddccda38376bafac.html
写这个题。。如果不好好优化一下自己的代码的话，是很有可能过不去的。。。
首先，要思考一下通过 Prim 存哪些数据，网上有一些题解存了好多不同的数据啊。。比如一条边是否在MST中啊 之类的。要知道，你存的数据越多，你后面维护的东西就越多，代码就越长，就越容易出错。这题后面就要维护这课MST，存那么多信息代码要很复杂的。
从 Prim 里得到什么？第一，数值。第二，这颗树都有哪些边，对于第二种信息，我们只要存下 pre[x] 数组就可以了，这些信息完全足够我们构建这课树，这就足够了。
这个代码分为3个部分吧
第一个是 Prim 部分，这部分代码。。就不用多说了。
然后更新成根节点度等于联通分量个数的MST
最后是递增到 K限制 的MST
这里面又涉及到两个函数，一个是 Best（x） 从这个函数里面我们想要知道什么信息呢？第一从root到x这条路径上最大的边是几，第二，这条边是哪条边。所以，我们返回信息的时候用个 pair 就好了嘛，而且，根本不需要预处理，随用随DP，又节省了好几行代码。
然后是update。因为我们的信息很简单，就是MST中的点和他老子，只要改这个信息就足够了，而需要改哪里呢？当一个点从某联通分量上连接到root，并且删掉一条边之后，这个联通分量的 root1（离root 最近的点）变了，所以，只需要把他以前的老子全变成儿子，就可以了嘛。所以update函数也非常好些只有那么几行。整个代码虽然思路复杂，但是因为维护的信息不多，后面还是很好写的。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <set>
#include <stack>
using namespace std;#define READ freopen("acm.in","r",stdin)
#define WRITE freopen("acm.out","w",stdout)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define MII map<int,int>::iterator
#define fst first
#define sec second
#define MS(x,d) memset(x,d,sizeof(x))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ROOT 0,n-1,1
#define PB push_back
#define FOR(a,b,c) for(int a=b;a<c;a++)
#define MOD 1000000007
#define keyTree (ch[ ch[root][1] ][0])
#define MAX 600
map<string,int> mp;
int G[MAX][MAX];
int pre[MAX];// MST
int used[MAX];// Prim 用
PII best[MAX];// 最大权值 所在边
int tim[MAX];// 判断是第几个连通分量里的点
int ans;
int n,k;
void Prim(int s)
{int dist[MAX];fill(dist,dist+MAX,INF);dist[s]=0;while(1){int t,mi=INF;for(int i=0;i<n;i++){if(!used[i]&&mi>dist[i])mi=dist[i],t=i;}if(mi==INF)return ;used[t]=1;tim[t]=s;ans+=dist[t];for(int i=0;i<n;i++){if(!used[i]&&G[i][t]!=-1&&G[i][t]<dist[i]){dist[i]=G[i][t];pre[i]=t;}}}
}PII Best(int x)
{if(pre[x]==0)// 与 ROOT 有关的点return PII(-1,0);if(best[x].fst!=-1)return best[x];if(G[pre[x]][x]>Best(pre[x]).fst)best[x]=PII(G[pre[x]][x],x);elsebest[x]=Best(pre[x]);return best[x];
}
void update(int v,int fa)
{if(pre[v]==-1){pre[v]=fa;return ;}update(pre[v],v);//交换儿子和老子pre[v]=fa;
}
void solve()
{int mark[MAX];MS(mark,0);used[0]=1;int cnt=0;for(int i=1;i<n;i++)if(!used[i]){cnt++;Prim(i);int mi=INF,t;for(int j=1;j<n;j++)//找到本连通分量中离 ROOT 最近的点if(tim[j]==i&&G[0][j]!=-1&&mi>G[0][j])mi=G[0][j],t=j;ans+=mi;update(t,0);//更新pre}for(int j=cnt;j<k;j++){int mi=INF,t;for(int i=0;i<n;i++)best[i].fst=-1;for(int i=1;i<n;i++)//找到最大的交换后能减小的数值{if(G[0][i]!=-1&&pre[i]!=0)if(G[0][i]-Best(i).fst<mi){mi=G[0][i]-Best(i).fst;t=i;}}if(mi==INF)return ;PII p=Best(t);if(p.fst>G[0][t]){ans+=G[0][t]-p.fst;pre[p.sec]=-1;//删除边update(t,0);}elsereturn ;}
}
int pid(string s)
{if(mp.find(s)!=mp.end())return mp[s];return mp[s]=n++;
}
void input(int m)
{n=0;mp["Park"]=n++;for(int i=0;i<m;i++){string f,t;int cost;cin>>f>>t>>cost;int ff,tt;ff=pid(f),tt=pid(t);if(G[ff][tt]==-1||G[ff][tt]>cost)G[ff][tt]=G[tt][ff]=cost;}cin>>k;
}
int main()
{READ;int m;while(cin>>m){MS(tim,-1);MS(used,0);mp.clear();ans=0;MS(G,-1);MS(pre,-1);input(m);solve();printf("Total miles driven: %d\n",ans);}return 0;
} 这篇关于POJ 1639 有度限制的最小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
