首页 > 代码库 > （最大k度限制生成树）POJ 1639 - Picnic Planning
（最大k度限制生成树）POJ 1639 - Picnic Planning
题意：
给一个无向带权图，图上有不超过20个人和1个公园，现在这些人想到公园去集合，他们可以直接去公园也可以，和其他人一起坐车去公园（假设他们的车容量无限），但是这个公园停车场只有k个位置，现在要求他们到达公园所需要的总花费。
分析：
乍一看是最小生成树，但是停车场只有k个位置，所以就限定了公园节点只能最多连k个人，也就是说有一个点的度数是给定了的。
想了很久，第一感觉就是想其他生成树那样，肯定要把边删去，从环中选择更优解， 按套路来说。
但是想了很久不知道怎么处理。
不过，看到题目只有20个人，k<20，可以从n个人中选出k个人，与停车场连接，然后跑最小生成树。虽然很暴力，但最大复杂度才C(20,10)*mlogm，看起来不是很大啊，也的的确确A了，但是跑了接近2s，显然POJ数据真的很水。
其实这题是经典的问题，国家队论文里有讲，据说刘汝佳黑书里也有。推荐一个不错的博客：http://blog.csdn.net/nacl__/article/details/52052133
没错，我就是抄他代码的，自己写半天感觉非常搓，不过，他的代码没有删边，
这句话有问题，我修改了一下。
最近看了一下生成树和最短路的题，感觉天天发现新大陆啊。
代码：
标程
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <bitset> 9 #include <string> 10 #include <cctype> 11 #include <cstdio> 12 #include <cstring> 13 #include <cstdlib> 14 #include <iostream> 15 #include <algorithm> 16 // #include <unordered_map> 17 18 using namespace std; 19 20 typedef long long ll; 21 typedef unsigned long long ull; 22 typedef pair<int, int> pii; 23 typedef pair<ull, ull> puu; 24 25 #define inf (0x3f3f3f3f) 26 #define lnf (0x3f3f3f3f3f3f3f3f) 27 #define eps (1e-9) 28 #define fi first 29 #define se second 30 31 bool sgn(double a, string select, double b) { 32 if(select == "==")return fabs(a - b) < eps; 33 if(select == "!=")return fabs(a - b) > eps; 34 if(select == "<")return a - b < -eps; 35 if(select == "<=")return a - b < eps; 36 if(select == ">")return a - b > eps; 37 if(select == ">=")return a - b > -eps; 38 } 39 40 41 //-------------------------- 42 43 const ll mod = 1000000007; 44 const int maxn = 30; 45 46 struct Edge { 47 int u, v, d; 48 Edge() {} 49 Edge(int a, int b, int c): u(a), v(b), d(c) {} 50 bool operator<(const Edge &e)const { 51 return d < e.d; 52 } 53 }; 54 55 int n, m, k; 56 int cnt; 57 int ans; 58 int parent[maxn]; 59 map<string, int> nodes; 60 vector<Edge>edges; 61 int g[maxn][maxn]; 62 bool tree[maxn][maxn]; 63 int minEdge[maxn]; 64 Edge dp[maxn]; 65 66 int find(int p) { 67 if(p == parent[p])return p; 68 else return parent[p] = find(parent[p]); 69 } 70 71 void un(int p, int q) { 72 parent[find(p)] = find(q); 73 } 74 75 void Kruskal() { 76 sort(edges.begin(), edges.end()); 77 for(int i = 0; i < edges.size(); i++) { 78 int p = edges[i].u; 79 int q = edges[i].v; 80 if(p == 1 || q == 1)continue; 81 if(find(p) != find(q)) { 82 un(p, q); 83 tree[p][q] = tree[q][p] = 1; 84 ans += edges[i].d; 85 } 86 } 87 } 88 89 void dfs(int cur, int pre) { 90 for(int i = 2; i <= cnt; i++) { 91 if(i == pre || !tree[cur][i])continue; 92 if(dp[i].d == -1) { 93 if(dp[cur].d > g[cur][i])dp[i] = dp[cur]; 94 else { 95 dp[i].u = cur; 96 dp[i].v = i; 97 dp[i].d = g[cur][i]; 98 } 99 }100 dfs(i, cur);101 }102 }103 104 105 void init() {106 memset(g, inf, sizeof(g));107 memset(tree, 0, sizeof(tree));108 memset(minEdge, inf, sizeof(minEdge));109 m = 0;110 cnt = 1;111 ans = 0;112 nodes["Park"] = 1;113 for(int i = 0; i < maxn; i++) {114 parent[i] = i;115 }116 }117 118 void solve() {119 scanf("%d", &n);120 string s1, s2;121 int d;122 init();123 for(int i = 1; i <= n; i++) {124 cin >> s1 >> s2 >> d;125 if(!nodes[s1])nodes[s1] = ++cnt;126 if(!nodes[s2])nodes[s2] = ++cnt;127 int u = nodes[s1];128 int v = nodes[s2];129 edges.push_back(Edge(u, v, d));130 g[u][v] = g[v][u] = min(g[u][v], d);131 }132 scanf("%d", &k);133 Kruskal();134 int keyPoint[maxn];135 for(int i = 2; i <= cnt; i++) {136 if(g[1][i] != inf) {137 int color = find(i);138 if(minEdge[color] > g[1][i]) {139 minEdge[color] = g[1][i];140 keyPoint[color] = i;141 142 }143 }144 }145 for(int i = 1; i <= cnt; i++) {146 if(minEdge[i] != inf) {147 m++;148 tree[1][keyPoint[i]] = tree[keyPoint[i]][1] = 1;149 ans += g[1][keyPoint[i]];150 }151 }152 for(int i = m + 1; i <= k; i++) {153 memset(dp, -1, sizeof(dp));154 dp[1].d = -inf;155 for(int j = 2; j <= cnt; j++)156 if(tree[1][j])157 dp[j].d = -inf;158 dfs(1, -1);159 int idx, minnum = inf;160 for(int j = 2; j <= cnt; j++) {161 if(minnum > g[1][j] - dp[j].d) {162 minnum = g[1][j] - dp[j].d;163 idx = j;164 }165 }166 if(minnum >= 0)167 break;168 tree[1][idx] = tree[idx][1] = 1;169 tree[dp[idx].u][dp[idx].v] = tree[dp[idx].v][dp[idx].u] = 0;170 ans += minnum;171 }172 printf("Total miles driven: %d\n", ans);173 }174 175 int main() {176 177 #ifndef ONLINE_JUDGE178 freopen("1.in", "r", stdin);179 // freopen("1.out", "w", stdout);180 #endif181 // iostream::sync_with_stdio(false);182 solve();183 return 0;184 }
暴力
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <bitset> 9 #include <string> 10 #include <cctype> 11 #include <cstdio> 12 #include <cstring> 13 #include <cstdlib> 14 #include <iostream> 15 #include <algorithm> 16 // #include <unordered_map> 17 18 using namespace std; 19 20 typedef long long ll; 21 typedef unsigned long long ull; 22 typedef pair<int, int> pii; 23 typedef pair<ull, ull> puu; 24 25 #define inf (0x3f3f3f3f) 26 #define lnf (0x3f3f3f3f3f3f3f3f) 27 #define eps (1e-9) 28 #define fi first 29 #define se second 30 31 bool sgn(double a, string select, double b) { 32 if(select == "==")return fabs(a - b) < eps; 33 if(select == "!=")return fabs(a - b) > eps; 34 if(select == "<")return a - b < -eps; 35 if(select == "<=")return a - b < eps; 36 if(select == ">")return a - b > eps; 37 if(select == ">=")return a - b > -eps; 38 } 39 40 41 //-------------------------- 42 43 const ll mod = 1000000007; 44 const int maxn = 100010; 45 46 int n, k; 47 48 map<string, int> name; 49 int cnt; 50 int edn; 51 int pkn; 52 53 struct Edge { 54 int u, v, c; 55 }; 56 57 bool cmp(Edge a, Edge b ) { 58 return a.c < b.c; 59 } 60 61 62 Edge raw_edges[500]; 63 Edge park_edges[500]; 64 Edge edges[500]; 65 66 string a, b; 67 int x; 68 69 int ans = inf; 70 71 int max_park; 72 73 int par[500]; 74 int findx(int x) { 75 if(par[x] == x)return x; 76 else return par[x] = findx(par[x]); 77 } 78 79 80 int Kruskal(int n) { 81 int m = edn + max_park; 82 for(int i = 0; i < n; i++) { 83 par[i] = i; 84 } 85 sort(edges, edges + m , cmp); 86 int cnt = 0; 87 int ans = 0; 88 for(int i = 0; i < m; i++) { 89 int u = edges[i].u; 90 int v = edges[i].v; 91 int c = edges[i].c; 92 int t1 = findx(u); 93 int t2 = findx(v); 94 if(t1 != t2) { 95 ans += c; 96 par[t1] = t2; 97 cnt++; 98 } 99 if(cnt == n - 1)break;100 }101 if(cnt < n - 1)return -1;102 else return ans;103 }104 105 106 int select[30];107 108 void dfs(int now, int pre) {109 if(now >= max_park) {110 for(int i = 0; i < edn; i++) {111 edges[i] = raw_edges[i];112 }113 int con = edn;114 for(int i = 0; i < now; i++) {115 edges[con++] = park_edges[select[i]];116 }117 int mins = Kruskal(cnt);118 // for(int i = edn; i < con; i++) {119 // printf("%d %d\n", edges[i].u, edges[i].v );120 // }121 // printf("res = %d\n", mins );122 if(mins != -1) {123 ans = min(ans, mins);124 }125 return ;126 }127 for(int i = pre + 1; i < pkn; i++) {128 select[now] = i;129 dfs(now + 1, i);130 }131 132 }133 134 135 void solve() {136 while(cin >> n) {137 cnt = edn = pkn = 0;138 ans = inf;139 name.clear();140 for(int i = 0; i < n; i++) {141 cin >> a >> b >> x;142 if(name.find(a) == name.end()) {143 name[a] = cnt++;144 }145 if(name.find(b) == name.end()) {146 name[b] = cnt++;147 }148 if(a == "Park" || b == "Park") {149 park_edges[pkn++] = Edge{name[a], name[b], x};150 } else {151 raw_edges[edn++] = Edge{name[a], name[b], x};152 }153 }154 scanf("%d", &k);155 max_park = min(pkn, k);156 dfs(0, -1);157 printf("Total miles driven: %d\n", ans);158 }159 160 161 }162 163 int main() {164 165 #ifndef ONLINE_JUDGE166 freopen("1.in", "r", stdin);167 freopen("1.out", "w", stdout);168 #endif169 // iostream::sync_with_stdio(false);170 solve();171 return 0;172 }
（最大k度限制生成树）POJ 1639 - Picnic Planning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。