ICPC 国内予選2016E 3Dプリント AOJ1612
解説
- 「各立方体は 0 個，1 個 または 2 個の立方体と重なることがあるが，3 個以上とは重ならない．」という条件から各立方体は鎖状もしくは環状になることがわかる。
- 任意の二つの立方体が重なるかどうかは少し考えればわかる（説明がめんどいので書かない）
- 重なりうる二つの立方体が重なった場合、どれだけの表面積を節約できるのかを求め配列に保存しておく。
- あとはその配列の情報を用いて、対象とするk個のつながった直方体の表面積を求め、それをひとつづつずらしていきその中の最小値を求めればよい。（ずらしていくときにqueueを使った）
- 頭が悪かったので鎖状のものと環状のものを同様に処理できなかったため、わざわざ似たような二つの処理を書いた。（グラフ慣れしていればいい感じに実装できそう）
#include <bits/stdc++.h> using namespace std; int INF = 1e9; int xyz[2010][3]; int d[2010][2010]; bool ch[2010]; int main(){ int n,k,s; while(true){ cin >> n >> k >> s; int plus = (s*s) * 6; if(n == 0)break; vector<int> G[2010]; int ans = INF; for(int i = 0;i < n;i++){ ch[i] = false; for(int j = 0;j < 3;j++){ cin >> xyz[i][j]; } } if(k == 1){ cout << (s*s)*6 << endl; continue; } for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ d[i][j] = -1; } } for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(i == j) continue; if(xyz[i][2] > xyz[j][2])continue; if(xyz[i][2] == xyz[j][2] && i > j)continue; if(xyz[i][2]+s >= xyz[j][2] && xyz[i][0]-s <= xyz[j][0] && xyz[i][0]+s >= xyz[j][0] && xyz[i][1]-s <= xyz[j][1] && xyz[i][1]+s >= xyz[j][1]){ G[i].push_back(j); G[j].push_back(i); int xx; int yy; if(xyz[i][0] < xyz[j][0]){ xx = xyz[i][0]+s - xyz[j][0]; }else{ xx = xyz[j][0]+s - xyz[i][0]; } if(xyz[i][1] < xyz[j][1]){ yy = xyz[i][1]+s-xyz[j][1]; }else{ yy = xyz[j][1]+s-xyz[i][1]; } int zz = xyz[i][2]+s-xyz[j][2]; d[i][j] = 2 * ( xx*zz + yy*zz + xx*yy); d[j][i] = d[i][j]; } } } for(int i = 0;i < n;i++){ if(ch[i] == true)continue; if(G[i].size() == 1){ ch[i] = true; int now = i; int pre = -1; int count = 1; int sum = plus; queue<int> que; while(true){ if(count == k){ ans = min(ans,sum); bool flag = true; for(int j = 0;j < G[now].size();j++){ if(pre != G[now][j] && ch[G[now][j]] == false){ pre = now; now = G[pre][j]; ch[now] = true; flag = false; break; } } if(flag)break; int q = que.front(); que.pop(); que.push(d[pre][now]); sum += q; sum -= d[pre][now]; ans = min(ans,sum); }else{ sum += plus; count++; bool flag = true; for(int j = 0;j < G[now].size();j++){ if(pre != G[now][j] && ch[G[now][j]] == false){ pre = now; now = G[pre][j]; ch[now] = true; flag = false; break; } } if(flag)break; que.push(d[pre][now]); sum -= d[pre][now]; } } } } for(int i = 0;i < n;i++){ if(ch[i] == true)continue; if(G[i].size() != 2)continue; ch[i] = true; int count = 1; int now = i; int pre = -1; int sum = (s*s)*6; queue<int> que; queue<int> num; num.push(-1); while(true){ if(count == k){ ans = min(ans,sum); int q = num.front(); num.pop(); if(q == -1 && d[now][i] != -1 && k != 2){ ans = min(ans,sum-d[now][i]); break; } if(q == i)break; for(int j = 0;j < G[now].size();j++){ if(pre != G[now][j]){ pre = now; now = G[pre][j]; que.push(d[now][pre]); num.push(now); ch[now] = true; break; } } q = que.front(); que.pop(); sum += q; sum -= d[now][pre]; ans = min(ans,sum); }else{ count++; bool endflag = false; for(int j = 0;j < G[now].size();j++){ if(pre != G[now][j]){ pre = now; now = G[pre][j]; if(now == i){ endflag = true; break; } que.push(d[now][pre]); num.push(now); ch[now] = true; break; } } if(endflag)break; sum += plus; sum -= d[now][pre]; } } } if(ans == INF){ cout << -1 << endl; }else{ cout << ans << endl; } } }
