主要写一些算法竞赛中
常用的模版和数据结构
重点是图的DFS BFS和连通快计数

拓扑排序和欧拉回路算法

双向链表的模拟

Boxes in a Line

BoxesLine

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//
//  main.cpp
//  BoxesLine
//
//  Created by zhangmin chen on 2019/4/18.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>

using namespace std;
typedef long long llong;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)

const int maxn = 100000 + 5;

class Node {
public:
    int data;
    Node *left, *right;
    
    Node() {
        data = 0;
        left = right = NULL;
    }
    bool operator== (const Node& rhs) const {
        return data == rhs.data;
    }
};

typedef Node* Nodep;

void link(Nodep l, Nodep r) {
    l->right = r;
    r->left = l;
}

Nodep nil;
Node box[maxn];

int N, M, OP;

void init(int n) {
    // box 0 is a nil
    
    nil = &(box[0]);
    nil->right = &(box[1]);
    nil->left = &(box[n]);
    for(int i = 1; i <= n; i++) {
        //
        Node& p = box[i];
        p.data = i;
        p.left = &(box[i-1]);
        p.right = &(box[(i+1) % (n+1)]);
    }
}

int main() {
    //
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int kase = 0;
    while(scanf("%d%d", &N, &M) == 2 && N) {
        //
        init(N);
        
        int x, y;
        int inv = 0;
    
        while(M--) {
            scanf("%d", &OP);
            
            if(OP == 4) {
                inv = 1 - inv;
            }
            else {
                if(inv && OP != 3) OP = 3 - OP;
                
                if(OP == 1) {
                    //
                    scanf("%d%d", &x, &y);
                    if(box[y].left->data == box[x].data) continue;
                    
                    link(box[x].left, box[x].right);
                    link(box[y].left, &box[x]);
                    link(&box[x], &box[y]);
                }
                else if(OP == 2) {
                    scanf("%d%d", &x, &y);
                    if(box[y].right->data == box[x].data) continue;
                    
                    link(box[x].left, box[x].right);
                    link(&box[x], box[y].right);
                    link(&box[y], &box[x]);
                }
                else if(OP == 3) {
                    scanf("%d%d", &x, &y);
                    if(box[y].right->data == box[x].data) {
                        //
                        link(&box[y], box[x].right);
                        link(box[y].left, &box[x]);
                        link(&box[x], &box[y]);
                    }
                    else if(box[x].right->data == box[y].data) {
                        //
                        link(&box[x], box[y].right);
                        link(box[x].left, &box[y]);
                        link(&box[y], &box[x]);
                    }
                    else {
                        //
                        Nodep yl = box[y].left;
                        Nodep yr = box[y].right;
                        
                        link(box[x].left, &box[y]);
                        link(&box[y], box[x].right);
                        link(yl, &box[x]);
                        link(&box[x], yr);
                    }
                }
            }
        }
        
        
        // finished!
        llong ans = 0;
        int cnt = 1;
        for(Nodep ptr = nil->right; ptr != nil; ptr = ptr->right, cnt++) {
            if(cnt % 2 == 1) ans += ptr->data;
        }
        
        if(inv && N % 2 == 0) ans = (llong) (N)*(N+1) / 2 - ans;
        printf("Case %d: %lld\n", ++kase, ans);
    }
}

树

树的遍历：递归遍历，前序，中序转换

Tree

LA5266

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
//
//  main.cpp
//  LA5266
//
//  Created by zhangmin chen on 2019/3/3.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <sstream>

#define debug(x) cout << #x << ": " << x << endl;
#define Set(x, v) memset(x, v, sizeof(x));

using namespace std;
const int maxn = 10000 + 10;
const int maxv = 0x3f3f3f3f;

struct Node {
    Node* left;
    Node* right;
    int val;
    Node(int x) {
        left = NULL;
        right = NULL;
        val = x;
    }
};

typedef Node *nodep;
int n;

bool read(int* ans) {
    string line;
    if(!getline(cin, line)) return false;
    stringstream ss(line);
    n = 0;
    int x;
    while(ss >> x) ans[n++] = x;
    return n > 0;
}

int inOrd[maxn], postOrd[maxn];

void init() {
    Set(inOrd, 0); Set(postOrd, 0);
}

// inorder[l1...r1], left + root + right
// postorder[l2...r2] left + right + root
nodep build(int l1, int r1, int l2, int r2) {
    if(l1 > r1) return 0;
    int val = postOrd[r2];
    
    nodep root = new Node(val);
    int p = l1;
    for(; p <= r1; p++) {
        if(inOrd[p] == val) break;
    }
    
    int cnt = p-l1;
    root->left = build(l1, p-1, l2, l2+cnt-1);
    root->right = build(p+1, r1, l2+cnt, r2-1);
    
    return root;
}

int bestw, bestsum;

void dfs(nodep u, int sum) {
    sum += u->val;
    if(u->left == NULL && u->right == NULL) {
        if(sum < bestsum || (sum == bestsum && u->val < bestw)) {
            bestw = u->val;
            bestsum = sum;
        }
    }
    if(u->left != NULL) dfs(u->left, sum);
    if(u->right != NULL) dfs(u->right, sum);
}


int main() {
    freopen("input.txt", "r", stdin);
    while (read(inOrd)) {
        read(postOrd);
        
        // build:
        nodep tree = build(0, n-1, 0, n-1);
        bestsum = maxv;
        dfs(tree, 0);
        printf("%d\n", bestw);
        init();
    }
}



四分树

根据树的信息进行递归输出

LA5206
LA5206

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//
//  main.cpp
//  LA5206-3
//
//  Created by zhangmin chen on 2019/3/7.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>

using namespace std;
typedef long long llong;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)

const int dx[] = {0, 0, 1, 1};
const int dy[] = {0, 1, 0, 1};
// nw, ne, sw, se

const int maxn = 64 + 10;
typedef long long llong;
typedef vector<int>::iterator VII;
typedef map<int, int>::iterator MII;
enum color{ White = 0, Black = 1, Gray = 2 };
//char img[maxn][maxn];
int grid[maxn][maxn];

int N;

struct POS {
    int x, y;
    POS(int x, int y) : x(x), y(y) {}
};

/** draw tree **/
vector<int> leafs;
// locate blocks and draw

void locate(int leaf, int& len, POS& pos) {
    len = N;
    pos.x = 0; pos.y = 0;
    
    while(leaf) {
        int dir = leaf % 5 - 1;
        len /= 2;
        
        //locate:
        pos.x += dx[dir]*len; pos.y += dy[dir]*len;
        leaf /= 5;
    }
}
void draw(vector<int>& leafs) {
    //Set(img, '.');
    Set(grid, 0);
    for(int i = 0; i < leafs.size(); i++) {
        int cur = leafs[i];
        int len;
        POS pos(0, 0);
        
        locate(cur, len, pos);
        
        _for(r, 0, len) _for(c, 0, len) grid[pos.x+r][pos.y+c] = 1;
        
    }
}

/** draw tree according to grid[][]  **/
struct Node {
    int color;
    Node* cld[4];
    Node() {
        Set(cld, NULL);
        color = -1;
    }
    void init() {
        Set(cld, NULL);
    }
};
typedef Node* Nodep;

Nodep build(POS& pos, int len) {
    Nodep nd =  new Node;

    int area = 0;
    _for(i, pos.x, pos.x+len) _for(j, pos.y, pos.y+len) area += grid[i][j];
    
    if(area == 0) {
        //
        nd->color = White;
        nd->init();
        return nd;
    }
    if(area == len*len) {
        //
        nd->color = Black;
        nd->init();
        return nd;
    }
    
    nd->color = Gray;
    int len2 = len/2;
    _for(i, 0, 4) {
        POS np(pos.x + dx[i]*len2, pos.y + dy[i]*len2);
        nd->cld[i] = build(np, len2);
    }
    return nd;
}
// tree = build()

void cal(Nodep root, vector<int>& path, vector<int>& ans) {
    if(root->color == White) return;
    if(root->color == Black) {
        int base = 1, sum = 0;
        _for(i, 0, path.size()) {
            sum += base * path[i];
            base *= 5;
        }
        ans.push_back(sum);
        return;
    }
    
    _for(d, 0, 4) {
        path.push_back(d+1);
        cal(root->cld[d], path, ans);
        path.pop_back();
    }
}



int main() {
    freopen("input.txt", "r", stdin);
    string line;
    for(int kase = 0; cin >> N && N; kase++) {
        //
        leafs.clear();
        if(kase) printf("\n");
        bool isGrid = N > 0; N = abs(N);
        
        if(isGrid) {
            // cin >> line
            _for(i, 0, N) {
                cin >> line;
                _for(j, 0, N) grid[i][j] = line[j] - '0';
            }
        } else {
            // cin >> leaf
            int val;
            while(cin >> val && val != -1) leafs.push_back(val);
            draw(leafs);
            // finished
        }
        
        printf("Image %d", kase+1);
        if(isGrid) {
            // build grid[][] tree
            POS st(0, 0);
            Nodep tree = build(st, N);
            vector<int> path, ans;
            cal(tree, path, ans);
            
            sort(ans.begin(), ans.end());
            _for(i, 0, ans.size()) {
                if(i % 12) printf(" "); else printf("\n");
                printf("%d", ans[i]);
            }
            printf("\n");
            printf("Total number of black nodes = %d\n", (int)ans.size());
            
        } else {
            //
            printf("\n");
            _for(i, 0, N) {
                _for(j, 0, N) printf("%c", grid[i][j] ? '*' : '.');
                printf("\n");
            }
        }
    }
}

图

bfs与dfs

这类问题的分析方法是
dr[] = {-1, 0, 1, 0}
dc[] = {0, -1, 0, 1}

Ancient Messages

AncientMessage

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
//
//  main.cpp
//  AncientMessage
//
//  Created by zhangmin chen on 2019/4/19.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>

using namespace std;
typedef long long llong;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)

const int maxh = 200 + 5;
const int maxw = 50 * 4 + 5;

int H, W;
// H += 2, W = W * 4 + 2;

char h2b[256][5];
int data[maxh][maxw], ccid[maxh][maxw];
char origin[maxh][maxw];

void init() {
    strcpy(h2b['0'], "0000");
    strcpy(h2b['1'], "0001");
    strcpy(h2b['2'], "0010");
    strcpy(h2b['3'], "0011");
    strcpy(h2b['4'], "0100");
    strcpy(h2b['5'], "0101");
    strcpy(h2b['6'], "0110");
    strcpy(h2b['7'], "0111");
    strcpy(h2b['8'], "1000");
    strcpy(h2b['9'], "1001");
    strcpy(h2b['a'], "1010");
    strcpy(h2b['b'], "1011");
    strcpy(h2b['c'], "1100");
    strcpy(h2b['d'], "1101");
    strcpy(h2b['e'], "1110");
    strcpy(h2b['f'], "1111");
}


void readData(const char h2b[][5], int maxr, int maxc) {
    // for i = 0 to row
    // char ch = origin[row][col]

    memset(data, 0, sizeof(data));
    //memset(origin, 0, sizeof(origin));
    memset(ccid, 0, sizeof(ccid));
    
    for(int r = 0; r < maxr; r++) for(int c = 0; c < maxc; c++) {
        char ch = origin[r][c];
        //debug(ch);
        
        // get h2b[ch][i]-'0'
        
        for(int i = 0; i < 4; i++) {
            // data restore value data[1..H][1..W]
            data[r+1][c * 4 + i + 1] = h2b[ch][i] - '0';
            //debug(h2b[ch][i] - '0');
        }
    }
    
    H += 2;
    W = W * 4 + 2;
    
    // Now data row [0, H)
    // col [0, W)
    
}

const char* code = "WAKJSD";
// count connected components

// 1 is the background ccid
// Message ccid start from [2...)
// main: cnt = 0 dfs(++cnt);
// ccid = 0, means have not visited!

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};

bool valid(int r, int c) {
    if(r >= 0 && r < H && c >= 0 && c < W) return true;
    else return false;
}

void dfs(int r, int c, int cnt) {
    ccid[r][c] = cnt;
    for(int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(valid(nr, nc) && ccid[nr][nc] == 0 && data[nr][nc] == data[r][c])
            dfs(nr, nc, cnt);
    }
}

// then solve()
// cnt = 0  -> if ccid == 0  dfs(++cnt)
// we solve black position, which is msg
// we can't get the specified words directely, but we have ccid
// regard ccid as words identity

vector<int> msg;
int msgID() {
    int cnt = 0;
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
        if(ccid[i][j] != 0) continue;
        
        dfs(i, j, ++cnt);
        if(data[i][j] == 1) msg.push_back(cnt);
    }
    return cnt;
}

// for i = msg to msg.size()
// msg[i] is the id of words, words[ccid[r][c]] point to the specified words
// recogonize(msg[i])


vector<set<int> > words;
// if it is a msg position, then cntHole()
void cntHole(int r, int c) {
    for(int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(valid(nr, nc) && data[nr][nc] == 0 && ccid[nr][nc] != 1) {
            //
            words[ccid[r][c]].insert(ccid[nr][nc]);
        }
    }
}

void decode() {
    int cnt = msgID();
    //debug(cnt);
    words.clear();
    words.resize(cnt+1);
    
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
        if(data[i][j] == 1) cntHole(i, j);
    }
}

char recognize(int id) {
    int cnt = (int)words[id].size();
    return code[cnt];
}
// usage: for i = 0 to msg.size
// int curid = msg[i]
// recognize(curid)


void fresh() {
    msg.clear();
    words.clear();
    memset(origin, 0, sizeof(origin));
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    
    int kase = 0;
    while(scanf("%d%d", &H, &W) && H) {
        for(int i = 0; i < H; i++)
            scanf("%s", origin[i]);
        
        readData(h2b, H, W);
        // then we finished init();
        
        /*
        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) cout << data[i][j];
            cout << endl;
        }
         */
        
        // try to solve()
        decode();
        
        vector<char> ans;
        for(int i = 0; i < msg.size(); i++) {
            int curid = msg[i];
            ans.push_back(recognize(curid));
            //debug(ans.size());
        }
        sort(ans.begin(), ans.end());
        
    
        
        
        printf("Case %d: ", ++kase);
        // print out Message
        for(int i = 0; i < ans.size(); i++) printf("%c", ans[i]);
        puts("");
        fresh();
        ans.clear();
    }
    
}

复杂bfs

HDU2771
HDU2771

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
//
//  main.cpp
//  HDU2771
//
//  Created by zhangmin chen on 2019/3/4.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

#define debug(x) cout << #x << ": " << x << endl
#define Set(x, v) memset(x, v, sizeof(x))
#define REP(i, l, r) for(int i = (l); i <= (r); i++)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

using namespace std;

const int maxw = 1000 + 1;
const int maxn = 50 + 10;

const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0};
const int dz[] = {0, 0, 0, 0, 1, -1};

int read() {
    int x; scanf("%d", &x); return x;
}


// get sculpture
int x0[maxn], y0[maxn], z0[maxn], x1[maxn], y1[maxn], z1[maxn];
int xs[maxn*2], ys[maxn*2], zs[maxn*2];
int nx, ny, nz;
// nx++, ny++, nz++

int color[maxn*2][maxn*2][maxn*2];


// discretize:
// x[0] is the smallest, x[1] is the largest
// x_from = getID(x, nx, x[0])   x_to = getID(x, nx, x[1])

// vol: (xs[i+1]-xs[i]) * (ys[i+1]-ys[i]) * (zs[i+1]-zs[i])
void discretize(int* x, int& n) {
    sort(x, x+n);
    n = unique(x, x+n) - x;
}

int getID(int* x, int n, int v) {
    return lower_bound(x, x+n, v) - x;
}


void init() {
    xs[0] = ys[0] = zs[0] = 0;
    xs[1] = ys[1] = zs[1] = maxw;
    nx = ny = nz = 2;
}


struct POS {
    int x, y, z;
    POS(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
    
    bool inRange() const {
        return x >= 0 && x < nx-1 && y >= 0 && y < ny-1 && z >= 0 && z < nz-1;
    }
    
    POS neighbor(int dir) {
        return POS(x+dx[dir], y+dy[dir], z+dz[dir]);
    }
    // POS np = pos.neighbor(), if(!np.inRange()) continue
    
    bool solid() const {
        return color[x][y][z] == 1;
    }
    void setVis() {
        color[x][y][z] = 2;
    }

    bool isVisted() const {
        return color[x][y][z] == 2;
    }
    
    // if (!np.isVisited()) que.push(np)
    
    int volume() const {
        return (xs[x+1]-xs[x]) * (ys[y+1]-ys[y]) * (zs[z+1]-zs[z]);
    }
    
    int area(int dir) const {
        if(dx[dir] != 0) return (ys[y+1] - ys[y]) * (zs[z+1] - zs[z]);
        else if(dy[dir] != 0) return (xs[x+1] - xs[x]) * (zs[z+1] - zs[z]);
        return (xs[x+1] - xs[x]) * (ys[y+1] - ys[y]);
    }
};

void bfs(int& vm, int& cm) {
    vm = cm = 0;
    POS start;
    
    queue<POS> que;
    start.setVis();
    que.push(start);
    
    while(!que.empty()) {
        POS fr = que.front(); que.pop();
        vm += fr.volume();
        
        for(int i = 0; i < 6; i++) {
            POS np = fr.neighbor(i);
            if(!np.inRange()) continue;
            
            if(np.solid()) cm += np.area(i);
            else if(!np.isVisted()) {
                np.setVis();
                que.push(np);
            }
        }
    }
    //debug(maxw*maxw*maxw);
    //debug(vm);
    vm = maxw * maxw * maxw - vm;
}

int m;
int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    kase = read();
    
    while(kase--) {
        init();
        
        m = read();
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d%d%d%d", &x0[i], &y0[i], &z0[i], &x1[i], &y1[i], &z1[i]);
            // I made a bug here
            //debug(x0[i]); debug(y0[i]); debug(z0[i]);
            x1[i] += x0[i]; y1[i] += y0[i]; z1[i] += z0[i];
            xs[nx++] = x0[i]; xs[nx++] = x1[i];
            ys[ny++] = y0[i]; ys[ny++] = y1[i];
            zs[nz++] = z0[i]; zs[nz++] = z1[i];
        }
        
        discretize(xs, nx);
        discretize(ys, ny);
        discretize(zs, nz);
        //debug(nx), debug(ny), debug(nz);
        
        // build sculpture"
        Set(color, 0);
        for(int i = 0; i < m; i++) {
            int xbeg = getID(xs, nx, x0[i]), xend = getID(xs, nx, x1[i]);
            //debug(xbeg), debug(xend);
            int ybeg = getID(ys, ny, y0[i]), yend = getID(ys, ny, y1[i]);
            int zbeg = getID(zs, nz, z0[i]), zend = getID(zs, nz, z1[i]);
            
            FOR(px, xbeg, xend) FOR(py, ybeg, yend) FOR(pz, zbeg, zend)
                color[px][py][pz] = 1;
            
        }
        
        // bfs():
        int cm, vm;
        bfs(vm, cm);
        
        printf("%d %d\n", cm, vm);
    }
}

Topo排序

topo排序的核心：必须是有向无环图
1、通过bool dfs(int u)判断是否存在环
2、判断是否可以进行toposort: bool toposort()

模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
init();

bool dfs(int u) {
    vis[u] = -1;
    _for(v, 0, n) {
        if(G[u][v]) {
            if(vis[v] < 0) return false;
            else if(!vis[v] && !dfs(v)) return false;
        }
    }
    vis[u] = 1;
    topo.push_back(u);
    return true;
}

bool toposort() {
    _for(u, 0, n) {
        if(!vis[u]) if(!dfs[u]) return false;
    }
    reverse(topo.begin(), topo.end());
    return true;
}

UVA10305

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
//
//  main.cpp
//  UVA10305
//
//  Created by zhangmin chen on 2019/5/21.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 1000;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int G[maxn][maxn], n, m;
int vis[maxn];
vector<int> topo;

void init() {
    Set(G, 0);
    Set(vis, 0);
    topo.clear();
}



bool dfs(int u) {
    vis[u] = -1;
    _for(v, 0, n) {
        if (G[u][v]) {
            if(vis[v] < 0) return false;
            // circle
            else if(!vis[v]) dfs(v);
        }
    }
    vis[u] = 1;
    topo.push_back(u);
    return true;
}

bool toposort() {
    _for(u, 0, n) {
        if(!vis[u]) if(!dfs(u)) return false;
    }
    reverse(topo.begin(), topo.end());
    return true;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &n, &m) == 2 && n) {
        //
        init();
        _for(i, 0, m) {
            int u, v;
            cin >> u >> v; u--; v--;
            G[u][v] = 1;
        }
        
        if(toposort()) {
            //
            _for(i, 0, n-1) printf("%d ", topo[i]+1);
            printf("%d\n", topo[n-1]+1);
        }
        else printf("No\n");
    }
}


欧拉回路

问题分析：

HDU1116

HDU1116
dfs判断连通

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
108
//
//  main.cpp
//  HDU1116
//
//  Created by zhangmin chen on 2019/5/22.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 100;
const int maxl = 2000 + 10;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int kase, G[maxn][maxn], vis[maxn];
int ideg[maxn], odeg[maxn];
int m, u, v;

const int N = 26;

void init() {
    Set(G, 0);
    Set(vis, 1);
    Set(ideg, 0);
    Set(odeg, 0);
}

void dfs(int u) {
    vis[u] = 1;
    _for(i, 0, N) {
        if(G[u][i] && !vis[i]) dfs(i);
    }
}
// find which node has been visited


int main() {
    freopen("input.txt", "r", stdin);
    char str[maxl];
    
    cin >> kase;
    while(kase--) {
        init();
        cin >> m;
        
        _for(i, 0, m) {
            scanf("%s", str);
            int u = str[0] - 'a';
            int v = str[strlen(str) - 1] - 'a';
            
            G[u][v] = 1;
            vis[u] = vis[v] = 0;
            ideg[v]++; odeg[u]++;
        }
        
        bool exist = 0;
        int root = 0, fromN = 0, toN = 0, odd = 0;
        
        _for(i, 0, N) {
            if(ideg[i] == odeg[i]) continue;
            else if(ideg[i] == odeg[i] + 1) toN++;
            else if(odeg[i] == ideg[i] + 1) {
                fromN++;
                root = i;
            }
            else odd++;
        }
        
        if(odd > 0) {
            printf("The door cannot be opened.\n");
            continue;
        }
        
        if( (fromN == 1 && toN == 1) || (fromN == 0 && toN == 0) ) exist = 1;
        else exist = 0;
        
        dfs(root);
        _for(i, 0, N) if(!vis[i]) exist = 0;
        
        if(exist) printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");
    }
}

欧拉回路：使用并查集求连通分量

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
//
//  main.cpp
//  HDU1116-2
//
//  Created by zhangmin chen on 2019/5/22.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 256;
const int maxl = 2000 + 10;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int deg[maxn], vis[maxn];
int pa[maxn];
int m, u, v;

void init() {
    Set(deg, 0);
    Set(vis, 0);
    Set(pa, 0);
}
void init_pa() {
    _rep(u, 'a', 'z') pa[u] = u;
}

int findset(int u) { return pa[u] != u ? pa[u] = findset(pa[u]) : u; }

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    
    while(kase--) {
        init();
        init_pa();
        scanf("%d", &m);
        
        int cc = 26;
        char word[maxl];
        
        scanf("%d", &m);
        _for(i, 0, m) {
            scanf("%s", word);
            char u = word[0], v = word[strlen(word) - 1];
            
            deg[u]++;
            deg[v]--;
            vis[u] = vis[v] = 1;
            
            int s1 = findset(u), s2 = findset(v);
            if(s1 != s2) {
                pa[s1] = s2;
                cc--;
            }
        }
        
        
        vector<int> pNode;
        _rep(ch, 'a', 'z') {
            if(!vis[ch]) cc--;
            else if(deg[ch] != 0) pNode.push_back(deg[ch]);
        }
        
        bool exist = false;
        if(cc == 1 && ( (pNode.empty()) || (pNode.size() == 2 && (pNode[0] == 1 || pNode[0] == -1)) ) ) exist = true;
        
        if(exist) printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");
    }
}


数据结构综合应用

有向环：图形粘合问题

LA6393

LA6393

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
//
//  main.cpp
//  LA6393
//
//  Created by zhangmin chen on 2019/5/23.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 52 + 5;
const int maxl = 10;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

int G[maxn][maxn], vis[maxn];

void init() {
    Set(G, 0);
    Set(vis, 0);
}

int ID(char a, char b) {
    return (a - 'A') * 2 + (b == '+' ? 0 : 1);
}

void connect(char a1, char a2, char b1, char b2) {
    if(a1 == '0' || b1 == '0') return;
    int u = ID(a1, a2), v = ID(b1, b2) ^ 1;
    G[u][v] = 1;
}

bool dfs(int u) {
    vis[u] = -1;

    _for(v, 0, maxn) {
        if(G[u][v]) {
            if(vis[v] < 0) return false;
            else if(!vis[v] && !dfs(v)) return false;
        }
    }
    
    vis[u] = 1;
    return true;
}

bool toposort() {
    _for(u, 0, maxn) {
        if(!vis[u]) if(!dfs(u)) return false;
    }
    return true;
}

int main() {
    freopen("input.txt", "r", stdin);
    int n;
    
    while(scanf("%d", &n) == 1 && n) {
        init();
        while(n--) {
            char cube[maxl];
            scanf("%s", cube);
            _for(i, 0, 4) _for(j, 0, 4) {
                if(i != j) connect(cube[i * 2], cube[i * 2 + 1], cube[j * 2], cube[j * 2 + 1]);
            }
        }
        // we get data
        // then find cycle by topo sort
        
        if(!toposort()) cout << "unbounded" << endl;
        else cout << "bounded" << endl;
    }
}

双向bfs求最短路和边相关最值

HDU3760

HDU3760

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//
//  main.cpp
//  HDU3760
//
//  Created by zhangmin chen on 2019/5/23.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 100000 + 10;
const int inf = 1000000000;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Edge {
public:
    int from, to, w;
    Edge(int f = 0, int t = 0, int w_ = 0) : from(f), to(t), w(w_) {}
};

vector<int> G[maxn];
int vis[maxn], d[maxn];
vector<Edge> edges;
int n;

void clearVis() {
    Set(vis, 0);
}

void init() {
    _for(i, 0, maxn) G[i].clear();
    clearVis();
    edges.clear();
    Set(d, 0);
}

void addEdge(int from, int to, int w) {
    edges.push_back((Edge){from, to, w});
    G[from].push_back((int)edges.size() - 1);
}


void revbfs() {
    d[n-1] = 0;
    vis[n-1] = true;
    
    queue<int> que;
    que.push(n-1);
    
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        
        _for(i, 0, G[u].size()) {
            Edge& e = edges[G[u][i]];
            if(!vis[e.to]) {
                vis[e.to] = true;
                d[e.to] = d[u] + 1;
                que.push(e.to);
            }
        }
    }
}

void bfs() {
    clearVis();
    vector<int> ans;
    ans.clear();
    
    vis[0] = true;
    vector<int> nodes;
    nodes.push_back(0);
    
    _for(level, 0, d[0]) {
        int minColor = inf;
        _for(i, 0, nodes.size()) {
            int u = nodes[i];
            _for(v, 0, G[u].size()) {
                Edge& e = edges[G[u][v]];
                if(d[u] == d[e.to] + 1)
                    minColor = min(minColor, e.w);
            }
        }
        
        ans.push_back(minColor);
        
        vector<int> nodes2;
        _for(i, 0, nodes.size()) {
            int u = nodes[i];
            _for(v, 0, G[u].size()) {
                Edge& e = edges[G[u][v]];
                if(!vis[e.to] && d[u] == d[e.to] + 1 && minColor == e.w) {
                    vis[e.to] = true;
                    nodes2.push_back(e.to);
                }
            }
        }
        
        nodes = nodes2;
    }
    
    printf("%d\n", (int)ans.size());
    printf("%d", ans[0]);
    _for(i, 1, ans.size()) printf(" %d", ans[i]);
    printf("\n");
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    scanf("%d", &kase);
    
    while(kase--) {
        int from, to, w, m;
        init();
        
        scanf("%d%d", &n, &m);
        while (m--) {
            scanf("%d%d%d", &from, &to, &w);
            addEdge(from-1, to-1, w);
            addEdge(to-1, from-1, w);
        }
        
        //get all graph data
        revbfs();
        bfs();
    }
}

Linux系统软件包的依赖关系

UVA506
UVA506

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
//
//  main.cpp
//  UVA506
//
//  Created by zhangmin chen on 2019/5/24.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 10000 + 10;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

vector<int> depends[maxn];
vector<int> pa[maxn];
int status[maxn];
int cnt = 0;

map<string, int> str2id;
string id2str[maxn];

vector<int> installed;

int ID(const string& item) {
    if(!str2id.count(item)) {
        //
        id2str[++cnt] = item;
        str2id[item] = cnt;
    }
    return str2id[item];
}


void init() {
    Set(status, 0);
    cnt = 0;
}

void list() {
    _for(i, 0, installed.size()) {
        int u = installed[i];
        cout << "   " << id2str[u] << endl;
    }
}

void install(int id, bool explicity) {
    //
    if(!status[id]) {
        // install id
        _for(i, 0, depends[id].size()) {
            int u = depends[id][i];
            install(u, false);
        }
        // dependencity has already been installed
        cout << "   Installing " << id2str[id] << endl;
        status[id] = explicity ? 1 : 2;
        
        installed.push_back(id);
    }
}


bool needed(int id) {
    //
    _for(i, 0, pa[id].size()) {
        int u = pa[id][i];
        if(status[u]) return true;
    }
    return false;
}

void rmv(int id, bool explicity) {
    //
    if( (explicity || status[id] == 2) && !needed(id) ) {
        status[id] = 0;
        installed.erase(find(installed.begin(), installed.end(), id));
        
        cout << "   Removing " << id2str[id] << endl;
        
        _for(i, 0, depends[id].size()) {
            int u = depends[id][i];
            rmv(u, false);
        }
    }
}


int main() {
    freopen("input.txt", "r", stdin);
    
    init();
    string line, cmd;
    while (getline(cin, line)) {
        cout << line << endl;
        stringstream ss(line);
        ss >> cmd;
        
        if(cmd[0] == 'E') break;
        if(cmd[0] == 'L') list();
        else {
            //
            string item1, item2;
            ss >> item1;
            int id1 = ID(item1);
            
            if(cmd[0] == 'D') {
                while (ss >> item2) {
                    int id2 = ID(item2);
                    depends[id1].push_back(id2);
                    pa[id2].push_back(id1);
                }
            }
            else if(cmd[0] == 'I') {
                //
                if(status[id1]) cout << "   " << item1 << " is already installed." << endl;
                else install(id1, true);
            }
            else {
                if(!status[id1]) cout <<  "   " << item1 << " is not installed." << endl;
                else if(needed(id1)) cout << "   " << item1 << " is still needed." << endl;
                else rmv(id1, true);
            }
        }
    }
}

DFS与几何：游戏战场穿越

HDU3767
HDU3767

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
108
109
//
//  main.cpp
//  HDU3767
//
//  Created by zhangmin chen on 2019/5/24.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int maxn = 1000 + 10;
const double width = 1000.0;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Circle {
public:
    double x, y, r;
    Circle(double x_ = 0.0, double y_ = 0.0, double r_ = 0.0) : x(x_), y(y_), r(r_) {}
};

Circle circles[maxn];
bool vis[maxn];

void init() {
    Set(vis, 0);
}

bool intersect(int id1, int id2) {
    double dist = sqrt( (circles[id1].x - circles[id2].x) * (circles[id1].x - circles[id2].x) + (circles[id1].y - circles[id2].y) * (circles[id1].y - circles[id2].y) );
    return dist < (circles[id1].r + circles[id2].r);
}

int n;
double l, r;

void border(int u) {
    if(circles[u].x - circles[u].r < 0) {
        double dist = sqrt( (circles[u].r * circles[u].r) - (circles[u].x * circles[u].x) );
        l = min(l, circles[u].y - dist);
    }
    
    if(circles[u].x + circles[u].r > width) {
        double dist = sqrt( (circles[u].r * circles[u].r) - (width - circles[u].x) * (width - circles[u].x) );
        r = min(r, circles[u].y - dist);
    }
}

bool dfs(int u) {
    //
    if(vis[u]) return false;
    vis[u] = true;
    
    if(circles[u].y - circles[u].r < 0) return true;
    
    _for(i, 0, n) {
        if(i == u) continue;
        if(intersect(u, i) && dfs(i)) return true;
    }
    border(u);
    return false;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d", &n) == 1) {
        init();
        bool ok = true;
        l = r = width;
        
        _for(i, 0, n) {
            scanf("%lf%lf%lf", &circles[i].x, &circles[i].y, &circles[i].r);
        }
        
        _for(i, 0, n) {
            if(circles[i].y + circles[i].r >= width && dfs(i)) {
                ok = false;
                break;
            }
        }
        
        if(ok) printf("0.00 %.2lf %.2lf %.2lf\n", l, width, r);
        else printf("IMPOSSIBLE\n");
    }
}