注意去除无效结点
// // main.cpp // PATA1074 // // Created by Phoenix on 2018/2/17. // Copyright © 2018年 Phoenix. All rights reserved. // #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 100010; struct Node { int data; int num; int next; int address; }node[maxn]; bool cmp1(Node a, Node b) { return a.num < b.num; } bool cmp2(Node a, Node b) { return a.num > b.num; } int main(int argc, const char * argv[]) { int begin, n, k; for(int i = 0; i < maxn; i++) { node[i].num = maxn; } scanf("%d %d %d", &begin, &n, &k); for(int i = 0; i < n; i++) { int add; scanf("%d", &add); node[add].address = add; scanf("%d %d", &node[add].data, &node[add].next); } int num = 0; while(begin != -1) { node[begin].num = num++; begin = node[begin].next; } sort(node, node + maxn, cmp1); for(int i = 0; i < num / k; i++) { sort(node + i * k, node + i * k + k, cmp2); } for(int i = 0; i < num - 1; i++) { printf("d %d d\n", node[i].address, node[i].data, node[i + 1].address); } printf("d %d -1\n", node[num - 1].address, node[num - 1].data); return 0; }