本文共 3034 字，大约阅读时间需要 10 分钟。
题意：
见黑书。
思路：
最小限制树模板题：
#include #include #include #include #include #include #include #include #include #include #include #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 1073741824#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 150#define N 35using namespace std;//freopen("din.txt","r",stdin);struct node{ int u,w; node(int _u,int _w) { u = _u; w = _w; } friend bool operator < (node a,node b) { return a.w > b.w; }};int dis[N],pre[N];int col[N],near[N];int Msd[N];int mat[N][N];priority_queue q;map mp;int res,n;int prim(int s,int id){ int res = 0,i; while (!q.empty()) q.pop(); q.push(node(s,0)); dis[s] = 0; while (!q.empty()) { node cur = q.top(); q.pop(); int u = cur.u; int w = cur.w; if (!col[u]) { col[u] = id; res += w; for (i = 1; i <= n; ++i) { if (!col[i] && mat[u][i] && dis[i] > mat[u][i]) { dis[i] = mat[u][i]; pre[i] = u; q.push(node(i,dis[i])); } } } } return res;}void dfs(int u,int fa,int maxside){ Msd[u] = maxside > mat[fa][u] ? maxside : mat[fa][u]; for (int i = 1; i <= n; ++i) { if (mat[u][i] && i != fa && (pre[u] == i || pre[i] == u)) dfs(i,u,Msd[u]); }}void solve(int k){ int i; for (i = 0; i <= n; ++i) { dis[i] = inf; col[i] = 0; pre[i] = 0; near[i] = 0; } col[0] = 1;//标记每一个最小生成树，先将根节点计入1 res = 0; int num = 0; for (i = 1; i <= n; ++i) { if (!col[i]) res += prim(i,++num);//分别计算最小生成树 } //计算每个最小生成树里距离s的最短距离 for (i = 1; i <= n; ++i) { int mk = col[i]; if (mat[0][i] && (near[mk] == 0 || mat[0][i] < mat[0][near[mk]])) near[mk] = i; } //连接每个最小生成树到根节点s的最短距离同时更新每个节点可能连接的最大边权值 CL(Msd,0); for (i = 1; i <= num; ++i) { res += mat[0][near[i]]; mat[0][near[i]] = mat[near[i]][0] = 0;//将该点消除 dfs(near[i],0,0);//求出改最小生成树以0为根节点的树根到每个节点之间的最大边权值 } k = k - num;//此时形成num度最小生成树 while (k--) { int tmp = 0;//找出Msd[tmp] - mat[0][tmp]的最大值 for (i = 1; i <= n; ++i) { if (mat[0][i] && (tmp == 0 || Msd[tmp] - mat[0][tmp] < Msd[i] - mat[0][i])) tmp = i; } if (Msd[tmp] <= mat[0][tmp]) break;//如果不能使度限制生成树继续减小跳出 res -= (Msd[tmp] - mat[0][tmp]); mat[0][tmp] = mat[tmp][0] = 0;//将改变置为0，表示不能再枚举了，已经加入最小限度生成树 // int p = 0; for (i = tmp; pre[i] != 0; i = pre[i]) { if (p == 0 || mat[p][pre[p]] < mat[i][pre[i]]) p = i; } pre[p] = 0; dfs(tmp,0,0); } printf("Total miles driven: %d\n",res);}int main(){ int i,m; string s1,s2; int w; while (~scanf("%d",&m)) { mp.clear(); CL(mat,0); mp["Park"] = 0; n = 0; //printf("%d\n",mp.count("Park")); for (i = 0; i < m; ++i) { cin>>s1>>s2>>w; if (!mp.count(s1)) mp[s1] = ++n; if (!mp.count(s2)) mp[s2] = ++n; int tx = mp[s1]; int ty = mp[s2]; //建图 if (!mat[tx][ty] || mat[tx][ty] > w) mat[tx][ty] = mat[ty][tx] = w; } int k; cin>>k; solve(k); } return 0;}
转载于:https://www.cnblogs.com/E-star/archive/2012/12/03/2800607.html