题意：给一个DAG，最多可以删去k条边，求字典序最大的拓扑序列。思路：贪心选取当前可选的最大编号即可，同时用线段树维护下。一个节点可以被选，当且仅当没有指向它的边。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <map> 6 #include <queue> 7 #include <cmath> 8 #include <vector> 9 #include <ctime> 10 #include <cctype> 11 12 using namespace std; 13 14 #define mem0(a) memset(a, 0, sizeof(a)) 15 #define lson l, m, rt << 1 16 #define rson m + 1, r, rt << 1 | 1 17 #define define_m int m = (l + r) >> 1 18 #define Rep(a, b) for(int a = 0; a < b; a++) 19 #define lowbit(x) ((x) & (-(x))) 20 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {} 21 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {} 22 23 typedef double db; 24 typedef long long LL; 25 26 const int dx[4] = {1, 0, -1, 0}; 27 const int dy[4] = {0, -1, 0, 1}; 28 const int maxn = 1e5 + 7; 29 const int maxm = 1e5 + 7; 30 const int MD = 1e9 +7; 31 const int INF = 1e9 + 7; 32 33 template<class edge> struct Graph { 34 vector<vector<edge> > adj; 35 Graph(int n) {adj.clear(); adj.resize(n + 5);} 36 Graph() {adj.clear(); } 37 void resize(int n) {adj.resize(n + 5); } 38 void add(int s, edge e){adj[s].push_back(e);} 39 void del(int s, edge e) {adj[s].erase(find(iter(adj[s]), e)); } 40 vector<edge>& operator [](int t) {return adj[t];} 41 }; 42 Graph<int> G, H; 43 int X; 44 struct Seg { 45 int minv[maxn << 2]; 46 void build(int l, int r, int rt) { 47 if (l == r) { 48 minv[rt] = H[l].size(); 49 return ; 50 } 51 define_m; 52 build(lson); 53 build(rson); 54 minv[rt] = min(minv[rt << 1], minv[rt << 1 | 1]); 55 } 56 void update(int p, int x, int l, int r, int rt) { 57 if (l == r) { 58 minv[rt] += x; 59 return ; 60 } 61 define_m; 62 if (p <= m) update(p, x, lson); 63 else update(p, x, rson); 64 minv[rt] = min(minv[rt << 1], minv[rt << 1 | 1]); 65 } 66 int get(int k, int l, int r, int rt) { 67 if (l == r) { 68 X = minv[rt]; 69 return l; 70 } 71 define_m; 72 if (minv[rt << 1 | 1] <= k) return get(k, rson); 73 return get(k, lson); 74 } 75 }; 76 Seg S; 77 int main() { 78 //freopen("in.txt", "r", stdin); 79 int n, m, k; 80 while (cin >> n >> m >> k) { 81 G.adj.clear(); 82 G.resize(n); 83 H.adj.clear(); 84 H.resize(n); 85 for (int i = 0, u, v; i < m; i++) { 86 scanf("%d%d", &u, &v); 87 G.add(u, v); 88 H.add(v, u); 89 } 90 S.build(1, n, 1); 91 for (int i = n; i; i--) { 92 int dot = S.get(k, 1, n, 1); 93 k -= X; 94 printf("%d%c", dot, i >= 2? ' ' : ' '); 95 S.update(dot, INF, 1, n, 1); 96 for (int j = 0; j < G[dot].size(); j++) { 97 S.update(G[dot][j], -1, 1, n, 1); 98 } 99 } 100 } 101 return 0; 102 }