我的妈呀，这码农神题......
第一问是个DP，要记录方案。先把纵向的转移建图。发现可以按照y坐标来划分阶段，每一层vector存一下，用前后缀最大值来转移。
第二问考虑所有可能成为最优方案的边。从终点倒推可以保证每条边都能到起点，而从起点出发就不一定能保证。这些边拿去网络流建图，然后最小流。
注意第二问找边的时候，每一层的点其实可以视作两个，经过同层转移的和未经过的。这两者不可混为一谈。
最小流先跑S -> T然后t -> s退流的话，要用当前弧优化，否则会被最后一个数据卡成n²。
#include <bits/stdc++.h>
const int N = , INF = 0x7f7f7f7f;
struct Node {
int x, y, id;
inline bool operator <(const Node &w) const {
if(y != w.y) return y < w.y;
return x < w.x;
}
}node[N];
inline void read(int &x) {
x = ;
char c = getchar();
bool f = ;
while(c < '' || c > '') {
if(c == '-') f = ;
c = getchar();
}
while(c >= '' && c <= '') {
x = x * + c - ;
c = getchar();
}
if(f) x = (~x) + ;
return;
}
struct Edge {
int nex, v;
}edge[N << ]; int tp;
int n, X[N << ], xx, bin[N << ], e[N], fr1[N], fr2[N], fr_l[N], fr_r[N], large_l[N], large_r[N], f[N], ff[N];
bool visit[N], visit2[N];
std::vector<int> v[N << ];
inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void out(int x, int flag) {
if(!node[x].id) return;
if(flag == ) {
out(fr1[x], );
}
else {
out(fr2[x], );
int y = fr2[x], u = node[y].y;
if(y == x) {
printf("%d ", node[x].id);
}
else if(node[y].x > node[x].x) {
for(int i = ; i < (int)(v[u].size()); i++) {
if(node[v[u][i]].x >= node[y].x) {
printf("%d ", node[v[u][i]].id);
}
}
for(int i = v[u].size() - ; i >= ; i--) {
int temp = node[v[u][i]].x;
if(temp < node[y].x && temp >= node[x].x) {
printf("%d ", node[v[u][i]].id);
}
}
}
else {
for(int i = v[u].size() - ; i >= ; i--) {
if(node[v[u][i]].x <= node[y].x) {
printf("%d ", node[v[u][i]].id);
}
}
for(int i = ; i < (int)(v[u].size()); i++) {
int temp = node[v[u][i]].x;
if(temp > node[y].x && temp <= node[x].x) {
printf("%d ", node[v[u][i]].id);
}
}
}
}
return;
}
namespace fl {
struct Edge {
int nex, v, c;
Edge(int Nex = , int V = , int C = ) {
nex = Nex;
v = V;
c = C;
}
}edge[]; int tp = ;
int e[N], vis[N], in[N], d[N], vis2[N], cur[N];
std::queue<int> Q;
inline void add(int x, int y, int z) {
edge[++tp] = Edge(e[x], y, z);
e[x] = tp;
edge[++tp] = Edge(e[y], x, );
e[y] = tp;
return;
}
inline void Add(int x, int y) {
/// x -> y [1, INF]
vis2[x] = vis2[y] = ;
add(x, y, N);
in[y]++;
in[x]--;
return;
}
inline bool BFS(int s, int t) {
static int Time = ; Time++;
vis[s] = Time;
d[s] = ;
Q.push(s);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(vis[y] != Time && edge[i].c) {
vis[y] = Time;
d[y] = d[x] + ;
Q.push(y);
}
}
}
return vis[t] == Time;
}
int DFS(int x, int t, int maxF) {
if(x == t) return maxF;
int ans = ;
for(int i = cur[x] ? cur[x] : e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[y] != d[x] + ) {
continue;
}
int temp = DFS(y, t, std::min(maxF - ans, edge[i].c));
if(!temp) d[y] = INF;
ans += temp;
edge[i].c -= temp;
edge[i ^ ].c += temp;
if(ans == maxF) break;
cur[x] = i;
}
return ans;
}
inline int dinic(int s, int t) {
int ans = ;
while(BFS(s, t)) {
memset(cur, , sizeof(cur));
ans += DFS(s, t, INF);
}
return ans;
}
inline void solve() {
int s = N - , t = N - , S = N - , T = N - ;
for(int i = ; i <= n; i++) {
if(!vis2[i]) continue;
add(s, i, N);
add(i, t, N);
}
int now = tp;
add(t, s, INF);
for(int i = ; i <= n; i++) {
if(in[i] > ) {
add(S, i, in[i]);
}
else if(in[i] < ) {
add(i, T, -in[i]);
}
}
int ans;
dinic(S, T);
ans = edge[now + ].c;
for(int i = now + ; i <= tp; i++) edge[i].c = ;
ans -= dinic(t, s);
printf("%d\n", ans);
return;
}
}
int main() {
read(n);
for(int i = ; i <= n; i++) {
read(node[i].x); read(node[i].y);
node[i].id = i;
X[++xx] = node[i].x;
X[++xx] = node[i].y;
X[++xx] = node[i].x + node[i].y;
X[++xx] = node[i].x - node[i].y;
}
++n; ++xx; /// the Node O
std::sort(node + , node + n + );
std::sort(X + , X + xx + );
xx = std::unique(X + , X + xx + ) - X - ;
for(int i = ; i <= n; i++) {
int temp = std::lower_bound(X + , X + xx + , node[i].x + node[i].y) - X;
if(bin[temp]) {
add(bin[temp], i);
}
bin[temp] = i;
}
memset(bin + , , xx * sizeof(int));
for(int i = ; i <= n; i++) {
int temp = std::lower_bound(X + , X + xx + , node[i].x - node[i].y) - X;
if(bin[temp]) {
add(bin[temp], i);
}
bin[temp] = i;
}
memset(bin + , , xx * sizeof(int));
for(int i = ; i <= n; i++) {
node[i].x = std::lower_bound(X + , X + xx + , node[i].x) - X;
node[i].y = std::lower_bound(X + , X + xx + , node[i].y) - X;
}
for(int i = ; i <= n; i++) {
if(bin[node[i].x]) {
add(bin[node[i].x], i);
}
bin[node[i].x] = i;
v[node[i].y].push_back(i);
}
/// Build Graph 1 Over
memset(f, ~0x3f, sizeof(f));
f[] = ;
for(int u = ; u <= xx; u++) {
if(!v[u].size()) continue;
int len = v[u].size();
for(int i = ; i < len; i++) {
int x = v[u][i];
ff[x] = f[x];
fr2[x] = x;
}
/// trans in row
for(int i = ; i < len; i++) {
int x = v[u][i];
if(i && f[x] < large_l[i - ]) {
large_l[i] = large_l[i - ];
fr_l[i] = fr_l[i - ];
}
else {
large_l[i] = f[x];
fr_l[i] = x;
}
}
for(int i = len - ; i >= ; i--) {
int x = v[u][i];
if(i < len - && f[x] < large_r[i + ]) {
large_r[i] = large_r[i + ];
fr_r[i] = fr_r[i + ];
}
else {
large_r[i] = f[x];
fr_r[i] = x;
}
}
for(int i = ; i < len; i++) {
int x = v[u][i];
if(i < len - && f[x] < large_r[i + ] + len - i - ) {
f[x] = large_r[i + ] + len - i - ;
fr2[x] = fr_r[i + ];
}
if(i && f[x] < large_l[i - ] + i) {
f[x] = large_l[i - ] + i;
fr2[x] = fr_l[i - ];
}
}
/// trans in cross / other
for(int i = ; i < len; i++) {
int x = v[u][i];
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(f[y] < f[x] + ) {
f[y] = f[x] + ;
fr1[y] = x;
}
}
}
}
/// DP OVER
int large_val = -INF, ans_pos = ;
for(int i = ; i <= n; i++) {
if(large_val < f[i]) {
large_val = f[i];
ans_pos = i;
}
}
printf("%d\n", large_val);
out(ans_pos, );
/// Out OVER
for(int i = ; i <= n; i++) {
if(f[i] == large_val) visit2[i] = ;
if(ff[i] == large_val) visit[i] = ;
}
for(int u = xx; u >= ; u--) {
if(!v[u].size()) continue;
int len = v[u].size();
/// build Flow Graph (this -> up)
for(int i = ; i < len; i++) {
int x = v[u][i];
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(visit[y] && ff[y] == f[x] + ) {
visit2[x] = ;
fl::Add(x, y);
}
}
if(visit2[x] && f[x] == ff[x]) {
visit[x] = ;
}
}
/// Find Edge in row (update)
for(int j = ; j < len; j++) {
int y = v[u][j];
if(!visit2[y]) continue;
for(int i = ; i < len; i++) {
int x = v[u][i];
if(visit[x]) continue;
/// x -> y
if(node[x].x < node[y].x && f[y] == ff[x] + j) {
visit[x] = ;
}
else if(node[y].x < node[x].x && f[y] == ff[x] + len - j - ) {
visit[x] = ;
}
}
}
}
puts("");
/// Build Flow Over
fl::solve();
return ;
}
AC代码
10k还行