# poj 1639 Picnic Planning 度限制mst

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

```  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 }```

## 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 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