我的妈呀，这码农神题......
第一问是个DP，要记录方案。先把纵向的转移建图。发现可以按照y坐标来划分阶段，每一层vector存一下，用前后缀最大值来转移。
第二问考虑所有可能成为最优方案的边。从终点倒推可以保证每条边都能到起点，而从起点出发就不一定能保证。这些边拿去网络流建图，然后最小流。
注意第二问找边的时候，每一层的点其实可以视作两个，经过同层转移的和未经过的。这两者不可混为一谈。
最小流先跑S -> T然后t -> s退流的话，要用当前弧优化，否则会被最后一个数据卡成n²。
1 #include <bits/stdc++.h> 2 3 const int N = 50010, INF = 0x7f7f7f7f; 4 5 struct Node { 6 int x, y, id; 7 inline bool operator <(const Node &w) const { 8 if(y != w.y) return y < w.y; 9 return x < w.x; 10 } 11 }node[N]; 12 13 inline void read(int &x) { 14 x = 0; 15 char c = getchar(); 16 bool f = 0; 17 while(c < '0' || c > '9') { 18 if(c == '-') f = 1; 19 c = getchar(); 20 } 21 while(c >= '0' && c <= '9') { 22 x = x * 10 + c - 48; 23 c = getchar(); 24 } 25 if(f) x = (~x) + 1; 26 return; 27 } 28 29 struct Edge { 30 int nex, v; 31 }edge[N << 2]; int tp; 32 33 int n, X[N << 2], xx, bin[N << 2], e[N], fr1[N], fr2[N], fr_l[N], fr_r[N], large_l[N], large_r[N], f[N], ff[N]; 34 bool visit[N], visit2[N]; 35 std::vector<int> v[N << 2]; 36 37 inline void add(int x, int y) { 38 tp++; 39 edge[tp].v = y; 40 edge[tp].nex = e[x]; 41 e[x] = tp; 42 return; 43 } 44 45 void out(int x, int flag) { 46 if(!node[x].id) return; 47 if(flag == 1) { 48 out(fr1[x], 2); 49 } 50 else { 51 out(fr2[x], 1); 52 int y = fr2[x], u = node[y].y; 53 if(y == x) { 54 printf("%d ", node[x].id); 55 } 56 else if(node[y].x > node[x].x) { 57 for(int i = 0; i < (int)(v[u].size()); i++) { 58 if(node[v[u][i]].x >= node[y].x) { 59 printf("%d ", node[v[u][i]].id); 60 } 61 } 62 for(int i = v[u].size() - 1; i >= 0; i--) { 63 int temp = node[v[u][i]].x; 64 if(temp < node[y].x && temp >= node[x].x) { 65 printf("%d ", node[v[u][i]].id); 66 } 67 } 68 } 69 else { 70 for(int i = v[u].size() - 1; i >= 0; i--) { 71 if(node[v[u][i]].x <= node[y].x) { 72 printf("%d ", node[v[u][i]].id); 73 } 74 } 75 for(int i = 0; i < (int)(v[u].size()); i++) { 76 int temp = node[v[u][i]].x; 77 if(temp > node[y].x && temp <= node[x].x) { 78 printf("%d ", node[v[u][i]].id); 79 } 80 } 81 } 82 } 83 return; 84 } 85 86 namespace fl { 87 struct Edge { 88 int nex, v, c; 89 Edge(int Nex = 0, int V = 0, int C = 0) { 90 nex = Nex; 91 v = V; 92 c = C; 93 } 94 }edge[1000010]; int tp = 1; 95 int e[N], vis[N], in[N], d[N], vis2[N], cur[N]; 96 std::queue<int> Q; 97 inline void add(int x, int y, int z) { 98 edge[++tp] = Edge(e[x], y, z); 99 e[x] = tp; 100 edge[++tp] = Edge(e[y], x, 0); 101 e[y] = tp; 102 return; 103 } 104 inline void Add(int x, int y) { 105 /// x -> y [1, INF] 106 vis2[x] = vis2[y] = 1; 107 add(x, y, N); 108 in[y]++; 109 in[x]--; 110 return; 111 } 112 inline bool BFS(int s, int t) { 113 static int Time = 0; Time++; 114 vis[s] = Time; 115 d[s] = 0; 116 Q.push(s); 117 while(!Q.empty()) { 118 int x = Q.front(); 119 Q.pop(); 120 for(int i = e[x]; i; i = edge[i].nex) { 121 int y = edge[i].v; 122 if(vis[y] != Time && edge[i].c) { 123 vis[y] = Time; 124 d[y] = d[x] + 1; 125 Q.push(y); 126 } 127 } 128 } 129 return vis[t] == Time; 130 } 131 int DFS(int x, int t, int maxF) { 132 if(x == t) return maxF; 133 int ans = 0; 134 for(int i = cur[x] ? cur[x] : e[x]; i; i = edge[i].nex) { 135 int y = edge[i].v; 136 if(!edge[i].c || d[y] != d[x] + 1) { 137 continue; 138 } 139 int temp = DFS(y, t, std::min(maxF - ans, edge[i].c)); 140 if(!temp) d[y] = INF; 141 ans += temp; 142 edge[i].c -= temp; 143 edge[i ^ 1].c += temp; 144 if(ans == maxF) break; 145 cur[x] = i; 146 } 147 return ans; 148 } 149 inline int dinic(int s, int t) { 150 int ans = 0; 151 while(BFS(s, t)) { 152 memset(cur, 0, sizeof(cur)); 153 ans += DFS(s, t, INF); 154 } 155 return ans; 156 } 157 inline void solve() { 158 int s = N - 5, t = N - 2, S = N - 3, T = N - 4; 159 for(int i = 1; i <= n; i++) { 160 if(!vis2[i]) continue; 161 add(s, i, N); 162 add(i, t, N); 163 } 164 int now = tp; 165 add(t, s, INF); 166 for(int i = 1; i <= n; i++) { 167 if(in[i] > 0) { 168 add(S, i, in[i]); 169 } 170 else if(in[i] < 0) { 171 add(i, T, -in[i]); 172 } 173 } 174 int ans; 175 dinic(S, T); 176 ans = edge[now + 2].c; 177 for(int i = now + 1; i <= tp; i++) edge[i].c = 0; 178 ans -= dinic(t, s); 179 printf("%d ", ans); 180 return; 181 } 182 } 183 184 int main() { 185 read(n); 186 for(int i = 1; i <= n; i++) { 187 read(node[i].x); read(node[i].y); 188 node[i].id = i; 189 X[++xx] = node[i].x; 190 X[++xx] = node[i].y; 191 X[++xx] = node[i].x + node[i].y; 192 X[++xx] = node[i].x - node[i].y; 193 } 194 ++n; ++xx; /// the Node O 195 std::sort(node + 1, node + n + 1); 196 std::sort(X + 1, X + xx + 1); 197 xx = std::unique(X + 1, X + xx + 1) - X - 1; 198 for(int i = 1; i <= n; i++) { 199 int temp = std::lower_bound(X + 1, X + xx + 1, node[i].x + node[i].y) - X; 200 if(bin[temp]) { 201 add(bin[temp], i); 202 } 203 bin[temp] = i; 204 } 205 memset(bin + 1, 0, xx * sizeof(int)); 206 for(int i = 1; i <= n; i++) { 207 int temp = std::lower_bound(X + 1, X + xx + 1, node[i].x - node[i].y) - X; 208 if(bin[temp]) { 209 add(bin[temp], i); 210 } 211 bin[temp] = i; 212 } 213 memset(bin + 1, 0, xx * sizeof(int)); 214 for(int i = 1; i <= n; i++) { 215 node[i].x = std::lower_bound(X + 1, X + xx + 1, node[i].x) - X; 216 node[i].y = std::lower_bound(X + 1, X + xx + 1, node[i].y) - X; 217 } 218 for(int i = 1; i <= n; i++) { 219 if(bin[node[i].x]) { 220 add(bin[node[i].x], i); 221 } 222 bin[node[i].x] = i; 223 v[node[i].y].push_back(i); 224 } 225 /// Build Graph 1 Over 226 memset(f, ~0x3f, sizeof(f)); 227 f[1] = 0; 228 for(int u = 1; u <= xx; u++) { 229 if(!v[u].size()) continue; 230 int len = v[u].size(); 231 for(int i = 0; i < len; i++) { 232 int x = v[u][i]; 233 ff[x] = f[x]; 234 fr2[x] = x; 235 } 236 /// trans in row 237 for(int i = 0; i < len; i++) { 238 int x = v[u][i]; 239 if(i && f[x] < large_l[i - 1]) { 240 large_l[i] = large_l[i - 1]; 241 fr_l[i] = fr_l[i - 1]; 242 } 243 else { 244 large_l[i] = f[x]; 245 fr_l[i] = x; 246 } 247 } 248 for(int i = len - 1; i >= 0; i--) { 249 int x = v[u][i]; 250 if(i < len - 1 && f[x] < large_r[i + 1]) { 251 large_r[i] = large_r[i + 1]; 252 fr_r[i] = fr_r[i + 1]; 253 } 254 else { 255 large_r[i] = f[x]; 256 fr_r[i] = x; 257 } 258 } 259 for(int i = 0; i < len; i++) { 260 int x = v[u][i]; 261 if(i < len - 1 && f[x] < large_r[i + 1] + len - i - 1) { 262 f[x] = large_r[i + 1] + len - i - 1; 263 fr2[x] = fr_r[i + 1]; 264 } 265 if(i && f[x] < large_l[i - 1] + i) { 266 f[x] = large_l[i - 1] + i; 267 fr2[x] = fr_l[i - 1]; 268 } 269 } 270 /// trans in cross / other 271 for(int i = 0; i < len; i++) { 272 int x = v[u][i]; 273 for(int i = e[x]; i; i = edge[i].nex) { 274 int y = edge[i].v; 275 if(f[y] < f[x] + 1) { 276 f[y] = f[x] + 1; 277 fr1[y] = x; 278 } 279 } 280 } 281 } 282 /// DP OVER 283 int large_val = -INF, ans_pos = 0; 284 for(int i = 1; i <= n; i++) { 285 if(large_val < f[i]) { 286 large_val = f[i]; 287 ans_pos = i; 288 } 289 } 290 printf("%d ", large_val); 291 out(ans_pos, 2); 292 /// Out OVER 293 for(int i = 1; i <= n; i++) { 294 if(f[i] == large_val) visit2[i] = 1; 295 if(ff[i] == large_val) visit[i] = 1; 296 } 297 for(int u = xx; u >= 1; u--) { 298 if(!v[u].size()) continue; 299 int len = v[u].size(); 300 /// build Flow Graph (this -> up) 301 for(int i = 0; i < len; i++) { 302 int x = v[u][i]; 303 for(int i = e[x]; i; i = edge[i].nex) { 304 int y = edge[i].v; 305 if(visit[y] && ff[y] == f[x] + 1) { 306 visit2[x] = 1; 307 fl::Add(x, y); 308 } 309 } 310 if(visit2[x] && f[x] == ff[x]) { 311 visit[x] = 1; 312 } 313 } 314 /// Find Edge in row (update) 315 for(int j = 0; j < len; j++) { 316 int y = v[u][j]; 317 if(!visit2[y]) continue; 318 for(int i = 0; i < len; i++) { 319 int x = v[u][i]; 320 if(visit[x]) continue; 321 /// x -> y 322 if(node[x].x < node[y].x && f[y] == ff[x] + j) { 323 visit[x] = 1; 324 } 325 else if(node[y].x < node[x].x && f[y] == ff[x] + len - j - 1) { 326 visit[x] = 1; 327 } 328 } 329 } 330 } 331 puts(""); 332 /// Build Flow Over 333 fl::solve(); 334 return 0; 335 }
10k还行