题目大意： 给定一些正方体的关系，要求一组符合这些关系的正方体坐标，如果不存在符合条件的正方体坐标，IMPOSSIBLE。(Special Judge)
实力还是太弱了，完全不会……
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107 |
#include <cstdio> #include <stdlib>#include <iostream>#define MAXN 2010#define MAXR 500000#define MAX 999999typedef
struct edges{ int
v,w,next;}edge;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];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]++;}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; 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); } for
(i=1; i<=R; i++){ char
t[10]; int
A, B; scanf("%s%d%d", t, &A, &B); 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;}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; while
(head != tail){ s[Q[head]] = count++; i = index[Q[head]]; 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;}int
main(){ int
Cases = 0, i; 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); 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.cnblogs.com/forever97/p/3561972.html