Hdu 3231 Box Relations
题目描述:
原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=3231
给定一些正方体的关系,要求一组符合这些关系的正方体坐标,如果不存在符合条件的正方体坐标,IMPOSSIBLE。(Special Judge)
题目分析:
首先把正方体这个立体问题拆分成X,Y,Z三个维度上的的平面问题。三个维度上的平面问题处理完了,正方体问题也就处理完了。
首先想到了差分约束系统,但是我的SPFA呃,TLE了……(求一个不TLE的差分约束系统标程……)
上网搜索了一个大牛的文,说只需要拓补排序就可以了,完全不需要差分约束。
再想一想,此题如果用差分约束系统来做,所有边权都是-1。其实不如更直观地进行构图,例如a<b,那么就构图map[a][b] = 1,也就是不妨看做a到b的边权为1。其实进行一下拓补排序,根据点的拓补排序的结果就可以直接作为答案输出,如果拓补排序失败也就是IMPOSSIBLE。
代码:
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) hdu3231
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define MAXN 2010
#define MAXR 500000
#define MAX 999999
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) typedef struct edges {
int v,w,next;
}edge;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int N, R;
edge edge_X[MAXR], edge_Y[MAXR], edge_Z[MAXR];
int s_X[MAXN], s_Y[MAXN], s_Z[MAXN];
int index_X[MAXN], index_Y[MAXN], index_Z[MAXN];
int degree_X[MAXN], degree_Y[MAXN], degree_Z[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Add(struct edges e[], int start, int end, int index[], int degree[], int &tot) {
e[tot].v = end;
e[tot].next = index[start];
index[start] = tot++;
degree[end]++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool init() {
int i, totx, toty, totz;
scanf("%d%d", &N, &R);
if (N == 0 && R == 0) return false;
memset(index_X, 255, sizeof(*index_X)*MAXN); //-1 indicates end of link
memset(index_Y, 255, sizeof(*index_Y)*MAXN);
memset(index_Z, 255, sizeof(*index_Z)*MAXN);
memset(degree_X, 0, sizeof(*degree_X)*MAXN);
memset(degree_Y, 0, sizeof(*degree_Y)*MAXN);
memset(degree_Z, 0, sizeof(*degree_Z)*MAXN);
totx = toty = totz = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (i=1; i<=N; i++) {
// node 0是超级汇点,最大的点。值为0
Add(edge_X, 0, i, index_X, degree_X, totx); //x1 of n-th Cube
Add(edge_Y, 0, i, index_Y, degree_Y, toty);
Add(edge_Z, 0, i, index_Z, degree_Z, totz);
Add(edge_X, i, i+N, index_X, degree_X, totx);
Add(edge_Y, i, i+N, index_Y, degree_Y, toty);
Add(edge_Z, i, i+N, index_Z, degree_Z, totz);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for (i=1; i<=R; i++) {
char t[10];
int A, B;
scanf("%s%d%d", t, &A, &B);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (t[0] == 'I') {
Add(edge_X, A, B+N, index_X, degree_X, totx); //x1(A) < x1(B)
Add(edge_X, B, A+N, index_X, degree_X, totx); //x2(A) > x1(B) or x1(B) < x2(A)
Add(edge_Y, A, B+N, index_Y, degree_Y, toty);
Add(edge_Y, B, A+N, index_Y, degree_Y, toty);
Add(edge_Z, A, B+N, index_Z, degree_Z, totz);
Add(edge_Z, B, A+N, index_Z, degree_Z, totz);
}
if (t[0] == 'X')
Add(edge_X, A+N, B, index_X, degree_X, totx); //x2(A) < x1(B)
if (t[0] == 'Y')
Add(edge_Y, A+N, B, index_Y, degree_Y, toty); //y2(A) < y1(B)
if (t[0] == 'Z')
Add(edge_Z, A+N, B, index_Z, degree_Z, totz); //z2(A) < z1(B)
}
return true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool NonPreFirstTopSort(edge e[], int index[], int degree[], int n, int s[]) {
int i, count(0), head(0), tail(1);
int Q[MAXN];
Q[0] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while (head != tail) {
s[Q[head]] = count++;
i = index[Q[head]];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while (i != -1) {
if (--degree[e[i].v] == 0) Q[tail++] = e[i].v;
i = e[i].next;
}
++head;
}
if (count < n) return false;
else return true;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int Cases = 0, i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while (init() && ++Cases) {
bool flag;
flag = NonPreFirstTopSort(edge_X, index_X, degree_X, N*2 + 1, s_X);
if (flag) flag = NonPreFirstTopSort(edge_Y, index_Y, degree_Y, N*2 + 1, s_Y);
if (flag) flag = NonPreFirstTopSort(edge_Z, index_Z, degree_Z, N*2 + 1, s_Z);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if (flag) {
printf("Case %d: POSSIBLE\n", Cases);
for (i=1; i<=N; i++)
printf("%d %d %d %d %d %d\n", s_X[i], s_Y[i], s_Z[i], s_X[i+N], s_Y[i+N], s_Z[i+N]);
printf("\n");
}
else
printf("Case %d: IMPOSSIBLE\n\n", Cases);
}
//system("pause");
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|