poj 1639 Picnic Planning 度限制mst

https://vjudge.net/problem/POJ-1639

题意:

有一群人,他们要去某一个地方,每个车可以装无数个人,给出了n条路,包含的信息有路连接的地方,以及路的长度,路是双向的,但是终点只有一个,并且终点能停的车的数量是有限制的,问最少走的路是多少。

思路:

因为终点的停车的数量是有限制的,所以终点的度是有限制的,又因为这题可以用最小生成树解决,所以就是度限制最小生成树。

度限制最小生成树求解思想并不复杂,首先我们把有度限制的点给忽略,然后给每一个连通分量求最小生成树,最后把每一个连通分量中与有度限制的点的距离最小的点与度限制点连接,假设有m个连通分量。

那么我们现在求出了m限制的最小生成树,假如限制数k < m,那么就无解。

当k >= m时,我们可以在m度限制mst的基础上,求m + 1,m + 2。。。k度限制最小生成树,求法也不是很难懂,但是程序就很难写了Orz。

如何求呢?枚举每一条未在生成树中与(现在我们把度限制点叫做R点)R点相连的边,然后把边加入生成树,必然会形成环,然后把环中与R点不相连的权值最大的边去掉,枚举之后的最小值就是m+1度限制最小生成树的值。然后依次求到k限制mst,求其中的最小值。

但是,依次枚举的话时间复杂度非常高,所以我们要优化。这时就用到了动态规划的思想。将与R点到其它点的边权值最大求出,之后加边的时候,直接替换就可以了。

转移方程 dp[v] = max(dp[father(v)],w(v , father(v)));

看不懂就多看几遍Orrrrrrrrrrrrrrrrrrrrrrrrz。

代码:

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <string.h>
  5 #include <map>
  6 #include <string>
  7 using namespace std;
  8
  9 const int inf = 0x3f3f3f3f;
 10
 11 struct edge
 12 {
 13     int x,y;
 14     int v;
 15 } a[5055],dp[5055];
 16
 17 map<string,int> mmp;
 18 bool flag[105][105];
 19 int par[105];
 20 int g[105][105];
 21
 22 int ans;
 23 int num;
 24 int du,lim;
 25
 26 int fin(int x)
 27 {
 28     if (x == par[x]) return x;
 29     else return par[x] = fin(par[x]);
 30 }
 31
 32 void unit(int x,int y)
 33 {
 34     x = fin(x);
 35     y = fin(y);
 36
 37     if (x == y) return;
 38
 39     par[x] = y;
 40 }
 41
 42 void dfs(int cur,int pre)
 43 {
 44     for (int i = 2;i <= num;i++)
 45     {
 46         if (i != pre && flag[cur][i])
 47         {
 48             if (dp[i].v == -1)
 49             {
 50                 if (dp[cur].v > g[cur][i])
 51                 {
 52                     dp[i] = dp[cur];
 53                 }
 54                 else
 55                 {
 56                     dp[i].x = cur;
 57                     dp[i].y = i;
 58                     dp[i].v = g[cur][i];
 59                 }
 60             }
 61
 62             dfs(i,cur);
 63         }
 64     }
 65 }
 66
 67 void solve(void)
 68 {
 69     for (int i = du + 1;i <= lim;i++)
 70     {
 71         memset(dp,-1,sizeof(dp));
 72
 73         dp[1].v = -inf;
 74
 75         for (int j = 2;j <= num;j++)
 76             if (flag[j][1]) dp[j].v = -inf;
 77
 78         dfs(1,-1);
 79
 80         int mi = inf,tmp;
 81
 82         for (int j = 2;j <= num;j++)
 83         {
 84             if (g[1][j] != -1)
 85             {
 86                 if (mi > g[1][j] - dp[j].v)
 87                 {
 88                     mi = g[1][j] - dp[j].v;
 89                     tmp = j;
 90                 }
 91             }
 92         }
 93
 94         if (mi >= 0) break;
 95
 96         ans += mi;
 97
 98         int x = dp[tmp].x,y = dp[tmp].y;
 99
100         flag[x][y] = flag[y][x] = 0;
101
102         flag[1][tmp] = flag[tmp][1] = 1;
103     }
104 }
105
106 int get_num(string aa)
107 {
108     if (mmp[aa]) return mmp[aa];
109     else
110     {
111         mmp[aa] = ++num;
112         return num;
113     }
114 }
115
116 bool cmp(edge aa,edge bb)
117 {
118     return aa.v < bb.v;
119 }
120
121 int main()
122 {
123     num = 1;
124
125     mmp["Park"] = 1;
126
127     memset(g,-1,sizeof(g));
128
129     int n;
130
131     scanf("%d",&n);
132
133     for (int i = 0;i < n;i++)
134     {
135         string aa,bb;
136         int v;
137
138         cin >> aa >> bb;
139
140         scanf("%d",&v);
141
142         int x = get_num(aa),y = get_num(bb);
143
144         if (g[x][y] == -1) g[x][y] = g[y][x] = v;
145         else g[x][y] = g[y][x] = min(v,g[x][y]);
146
147         a[i].x = x;
148         a[i].y = y;
149         a[i].v = g[x][y];
150     }
151
152     for (int i = 0;i <= num;i++) par[i] = i;
153
154     scanf("%d",&lim);
155
156     sort(a,a+n,cmp);
157
158     for (int i = 0;i < n;i++)
159     {
160         int x = a[i].x,y = a[i].y;
161
162         if (x == 1 || y == 1) continue;
163         if (fin(x) == fin(y)) continue;
164
165         ans += a[i].v;
166
167         unit(x,y);
168
169         flag[x][y] = flag[y][x]  =1;
170     }
171
172     int minn[105],tmp[105];
173
174     memset(minn,inf,sizeof(minn));
175
176     for (int i = 2;i <= num;i++)
177     {
178         int rt = fin(i);
179
180         if (g[1][i] != -1)
181         {
182             if (g[1][i] < minn[rt])
183             {
184                 minn[rt] = g[1][i];
185                 tmp[rt] = i;
186             }
187         }
188     }
189
190     for (int i = 2;i <= num;i++)
191     {
192         if (minn[i] != inf)
193         {
194             du++;
195             flag[1][tmp[i]] = flag[tmp[i]][1] = 1;
196             ans += minn[i];
197         }
198     }
199
200     solve();
201
202     printf("Total miles driven: %d\n",ans);
203
204     return 0;
205 }
时间: 08-21

poj 1639 Picnic Planning 度限制mst的相关文章

(最大k度限制生成树)POJ 1639 - Picnic Planning

题意: 给一个无向带权图,图上有不超过20个人和1个公园,现在这些人想到公园去集合,他们可以直接去公园也可以,和其他人一起坐车去公园(假设他们的车容量无限),但是这个公园停车场只有k个位置,现在要求他们到达公园所需要的总花费. 分析: 乍一看是最小生成树,但是停车场只有k个位置,所以就限定了公园节点只能最多连k个人,也就是说有一个点的度数是给定了的. 想了很久,第一感觉就是想其他生成树那样,肯定要把边删去,从环中选择更优解, 按套路来说. 但是想了很久不知道怎么处理. 不过,看到题目只有20个人

POJ 1639 Picnic Planning(初遇最小度限制生成树)

这是最小度限制生成树的经典问题,题意就不说了 题目链接:http://poj.org/problem?id=1639 一般都是1个顶点的度有限制k,如果每个顶点的度都有限制,那么当前是NP难的. 为了解决这个题目,先把限制度数的点设为V0点,那么把这一点先除外,那么剩下的点都没有度数限制,所有先对他们进行分析,把他们求生成森林后,假设得到t个连通分量,所以为了生成一棵把v0包含在内的树,必须让v0的度数限制度数k>=t,如果<t,无解. 接下来k度中已经用掉了t度,如何求从t度到k度的最小生成

K度限制MST poj 1639

/* k度限制MST:有一个点的度<=k的MST poj 1639 要求1号点的度不超过k 求MST 我们先把1号点扔掉 跑MST 假设有sum个连通分支 然后把这sum个分支连到1上 就得到了一个sum度的MST 这里往上连的时候 我们连这个分支里 距离1最近的 然后我们在1上加一条边 (即加一个度)得到sum+1度的MST 这里加边的时候 1连出去的每一条边都试一遍 取最小 假设当前1连到了 i 因为原来是个树 这样一搞就形成一个环 我们现在要删去环里面最长边 来得到更小的ans 我么维护d

poj1639,uva1537,uvalive2099,scu1622,fzu1761 Picnic Planning (最小限制生成树)

Picnic Planning Time Limit: 5000MS   Memory Limit: 10000K Total Submissions: 10742   Accepted: 3885 Description The Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of the

POJ 1659 Frogs&#39; Neighborhood(度序列构图)

题意  中文 根据Havel-Hakimi定理构图就行咯  先把顶点按度数从大到小排序  可图的话  度数大的顶点与它后面的度数个顶点相连肯定是满足的  出现了-1就说明不可图了 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 20; int mat[N][N], ord[N]; bool cmp(int i, int j) { retur

HDU 1102 &amp;&amp; POJ 2421 Constructing Roads (经典MST~Prim)

链接:http://poj.org/problem?id=2421  或   http://acm.hdu.edu.cn/showproblem.php?pid=1102 Problem Description There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We

【POJ 1639】 Picnic Planning (最小k度限制生成树)

[题意] 有n个巨人要去Park聚会.巨人A和先到巨人B那里去,然后和巨人B一起去Park.B君是个土豪,他家的停车场很大,可以停很多车,但是Park的停车场是比较小.只能停k辆车.现在问你在这个限制条件下.巨人到达Park的最短距离. 如果把那个条件去掉.那么就是就是求最小生成树.加上那个条件其实就是求顶点度数限制为k的最小生成树. Input Input will consist of one problem instance. The first line will contain a s

poj1639 Picnic Planning,K度限制生成树

题意: 矮人虽小却喜欢乘坐巨大的轿车,车大到可以装下无论多少矮人.某天,N(N≤20)个矮人打算到野外聚餐.为了集中到聚餐地点,矮人A 要么开车到矮人B 家中,留下自己的轿车在矮人B 家,然后乘坐B 的轿车同行:要么直接开车到聚餐地点,并将车停放在聚餐地.虽然矮人的家很大,可以停放无数量轿车,但是聚餐地点却最多只能停放K 辆轿车.给你一张加权无向图,描述了N 个矮人的家和聚餐地点,求出所有矮人开车最短总路程. 单点K度限制最小生成树 算法步骤: 1.求出除去K度点的最小生成森林,设森林数为m 2

POJ 3241 Object Clustering(Manhattan MST)

题目链接:http://poj.org/problem?id=3241 Description We have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes a and b (a, b ≤ 500). The resemblance of ob