BZOJ 4200 - [Noi2015]小园丁与老司机
Published on 2016-05-15描述
UOJ 传送门：【NOI2015】小园丁与老司机
分析
这题超级麻烦，如果不太会这种 DAG 上的 DP + 同层转移，也不会上下界的网络流的话，恐怕真的是灾难。
对于不会 上下界的网络流 的同学，建议先直接用我代码里面的模版，AC 之后再自己写一遍。
用法：调用：先
addEdge(from, to, bound, cap)，然后调用maxFlow(s, t)会返回最小流，如果没有可行流，返回 -1。
直接说这个题的正解了。
加入点 表示原点，下标为 0。
对于输出的 1， 2 行，我们使用 DAG 上的 DP + 同层转移来解决。因为没有 的点，所以我们按 坐标分层， 坐标相同的在一层，不同层 坐标依次递增。不同层之间连向上边和两个斜边，同层不连边。
这个怎么做到呢？我们先把所有点按 为第一关键字， 为第二关键字排序。如果排好序后 坐标为 的点的下标范围是 的话，我们连边 表示向上边。由于必须到达该方向上距离最近的尚未许愿的树且没有向下边，所以只能这样连。
接着看斜边，观察到所有为右上 关系的点，必定满足 ，k 是一个定值。所以把所有点按 为第一关键字， 为第二关键字排序，与刚刚一样做就行了。而所有为左上 关系的点，必定满足 ，k 是一个定值，所以把所有点按 为第一关键字， 为第二关键字排序，与刚刚一样做就行了。
连边完毕。考虑 DP，设 为从原点出发到 最多能经过多少个点（不含原点），初始值都为 ，，则 就是答案。
DP 的过程。按 分层， 从小到大一层的做。做到某一层的时候，这一层不考虑同层转移的值已经求出来了，那么这一层进行同层转移（可从左边，右边向某个点转移，预处理一下即可 ），转移完毕后利用连接的边更新高一层的答案。
打印解。这个可以从某个最优点开始，一直找是谁能转移到它，与之前的 DP 类似，注意有 2 种转移。
标记所有在最优策略上的边。这个极为麻烦，要倒着做，一开始标记所有最优点，接着所有能转移到最优点的边要标记。转移的时候有同层和不同层的区别，要记录某个点是否经过两次转移还是一次转移爬上更高一层。
细节很多很多，不可能说全，我代码有比较详细的注释，大家可以看看。
这篇写的很敷衍，真的是细节太多了啊，说不完。
代码
// Created by Sengxian on 5/14/16. // Copyright (c) 2016年 Sengxian. All rights reserved. // BZOJ 4200 NOI 2015 D2T3 有上下界网络流 + dp #include <bits/stdc++.h> using namespace std; typedef long long ll; inline int ReadInt() { static int n, ch; static bool flag; n = 0, ch = getchar(), flag = false; while (!isdigit(ch)) flag |= ch == '-', ch = getchar(); while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar(); return flag ? -n : n; } const int maxn = 50000 + 3, INF = 0x3f3f3f3f; struct edge { int to, cap, rev; bool real; edge(int to = 0, int cap = 0, int rev = 0): to(to), cap(cap), rev(rev) {} }; struct DinicWithBound { static const int maxNode = maxn + 10; vector<edge> G[maxNode]; int level[maxNode], iter[maxNode]; inline void addEdge(int f, int t, int c) { G[f].push_back(edge(t, c, G[t].size())); G[t].push_back(edge(f, 0, G[f].size() - 1)); } bool Bfs(int s, int t) { memset(level, -1, sizeof level); queue<int> q; level[s] = 0; q.push(s); while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = 0; i < (int)G[cur].size(); ++i) { edge &e = G[cur][i]; if (e.cap && level[e.to] == -1) { level[e.to] = level[cur] + 1; q.push(e.to); } } } return ~level[t]; } int Dfs(int cur, int flow, int t) { if (cur == t || flow == 0) return flow; for (int &i = iter[cur]; i < (int)G[cur].size(); ++i) { edge &e = G[cur][i]; if (e.cap && level[e.to] == level[cur] + 1) { int d = Dfs(e.to, min(flow, e.cap), t); if (d) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int maxFlow(int s, int t) { int d, flow = 0; while (Bfs(s, t)) { memset(iter, 0, sizeof iter); while (d = Dfs(s, INF, t), d) flow += d; } return flow; } int in[maxNode]; inline void addEdge(int f, int t, int b, int c) { in[f] -= b; //必须流 in[t] += b; //必须流 addEdge(f, t, c - b); //自由流 } int minFlow(int s, int t) { int S = t + 1, T = S + 1, allFlow = 0; for (int i = 0; i <= t; ++i) if (in[i] > 0) addEdge(S, i, in[i]), allFlow += in[i]; else if (in[i] < 0) addEdge(i, T, abs(in[i])); int idx = G[s].size(); addEdge(t, s, INF); if (maxFlow(S, T) != allFlow) return -1; int flow = 0; { edge &e = G[s][idx]; flow = e.cap; e.cap = G[e.to][e.rev].cap = 0; } for (int i = 0; i < G[S].size(); ++i) { edge &e = G[S][i]; e.cap = G[e.to][e.rev].cap = 0; } for (int i = 0; i < G[T].size(); ++i) { edge &e = G[T][i]; e.cap = G[e.to][e.rev].cap = 0; } return flow - maxFlow(t, s); } }Dinic; struct point { int x, y, id; point(int x = 0, int y = 0, int id = 0): x(x), y(y), id(id) {} bool operator < (const point &p) const { return y < p.y || (y == p.y && x < p.x); } inline void get() {x = ReadInt(), y = ReadInt();} }ps[maxn], ori_ps[maxn]; vector<int> G[maxn], rG[maxn]; int n; inline bool cmp1(const point &p1, const point &p2) {return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);} inline bool cmp2(const point &p1, const point &p2) {return (p1.x + p1.y) < (p2.x + p2.y) || ((p1.x + p1.y) == (p2.x + p2.y) && p1.y < p2.y);} inline bool cmp3(const point &p1, const point &p2) {return (p1.x - p1.y) < (p2.x - p2.y) || ((p1.x - p1.y) == (p2.x - p2.y) && p1.y < p2.y);} void process() { sort(ps, ps + n, cmp1); for (int i = 0; i < n - 1; ++i) if (ps[i].x == ps[i + 1].x) G[ps[i].id].push_back(ps[i + 1].id), rG[ps[i + 1].id].push_back(ps[i].id); sort(ps, ps + n, cmp2); for (int i = 0; i < n - 1; ++i) if ((ps[i].x + ps[i].y) == (ps[i + 1].x + ps[i + 1].y)) G[ps[i].id].push_back(ps[i + 1].id), rG[ps[i + 1].id].push_back(ps[i].id); sort(ps, ps + n, cmp3); for (int i = 0; i < n - 1; ++i) if ((ps[i].x - ps[i].y) == (ps[i + 1].x - ps[i + 1].y)) G[ps[i].id].push_back(ps[i + 1].id), rG[ps[i + 1].id].push_back(ps[i].id); // 不加横向边是因为会破坏DAG，所以要分层处理 } int d[maxn], f[maxn], l[maxn], r[maxn], id[maxn], pre[maxn]; map<int, int> lb, rb; void dp() { sort(ps, ps + n); fill(d, d + n, -INF); d[ps[0].id] = 0; //d[i] 到 i 最多可以经过多少个点 for (int i = 0; i < n; ++i) id[ps[i].id] = i; for (int i = 0, j = 0; i < n; i = j) { for (j = i; ps[j].y == ps[j + 1].y; ++j); //找到这一层的末尾 ++j; lb[ps[i].y] = i, rb[ps[i].y] = j; r[j] = -INF; for (int k = i; k < j; ++k) f[ps[k].id] = d[ps[k].id]; //不考虑同层转移的值 for (int k = i; k < j; ++k) l[k] = max(k == i ? -INF : l[k - 1], d[ps[k].id]); // 更新左边的最值 for (int k = j - 1; k >= i; --k) r[k] = max(r[k + 1], d[ps[k].id]); // 更新右边的最值 for (int k = i; k < j; ++k) { //可以到从之前某个点上到这一层，再走到边界，再走到 k，这就是同层转移的过程 int lv = (k == i ? -INF : l[k - 1]) + (k - i); int rv = r[k + 1] + (j - k - 1); d[ps[k].id] = max(d[ps[k].id], max(lv, rv)); } for (int k = i; k < j; ++k) { int u = ps[k].id; for (int x = 0; x < (int)G[u].size(); ++x) { int v = G[u][x]; if (d[v] < d[u] + 1) pre[v] = u; d[v] = max(d[v], d[u] + 1); } } } } int Max = 0; void printSolution() { int cur = 0; for (int i = 0; i < n; ++i) if (d[i] > Max) Max = d[i], cur = i; printf("%d\n", Max); vector<int> vec; int *use = d; while (cur) { vec.push_back(cur); bool flag = false; //非同层转移（即用G转移） for (int i = 0; i < rG[cur].size(); ++i) { int v = rG[cur][i]; if (d[v] + 1 == use[cur]) { use = d; //又可以同层转移了 cur = v, flag = true; break; } } if (flag) continue; use = f; //到这里，下一波不能同层转移。 //同层转移 int l = lb[ori_ps[cur].y], r = rb[ori_ps[cur].y]; for (int i = l; i < id[cur]; ++i) if (d[cur] == f[ps[i].id] + (id[cur] - l)) { for (int k = id[cur] - 1; k > i; --k) vec.push_back(ps[k].id); for (int k = l; k < i; ++k) vec.push_back(ps[k].id); cur = ps[i].id; flag = true; break; } if (flag) continue; for (int i = id[cur] + 1; i < r; ++i) if (d[cur] == f[ps[i].id] + (r - id[cur] - 1)) { for (int k = id[cur] + 1; k < i; ++k) vec.push_back(ps[k].id); for (int k = r - 1; k > i; --k) vec.push_back(ps[k].id); cur = ps[i].id; flag = true; break; } assert(flag); } for (int i = vec.size() - 1; ~i; --i) printf("%d%c", vec[i], i ? ' ' : '\n'); } bool mark[maxn]; int type[maxn]; void solve() { set<int> dict; int s = n, t = n + 1; for (int i = 0; i < n; ++i) Dinic.addEdge(s, i, 0, INF), Dinic.addEdge(i, t, 0, INF); for (int i = n - 1, j; ~i; i = j - 1) { for (j = i; j && ps[j].y == ps[j - 1].y; --j); //找到这一层的起始位置 //开始考虑非同层转移 //type & 1 的，表示这个点由一次同层转移一次非同层转移爬上去，故判 f //type & 2 的，表示这个点由一次非同层转移同层爬上去，故判 d for (int k = j; k <= i; ++k) { int u = ps[k].id; if (d[u] == Max) mark[u] = true, type[u] |= 2; //2 表示可转移到 d for (int t = 0; t < (int)G[u].size(); ++t) { int v = G[u][t]; if (mark[v] && ((type[v] & 2) && d[u] + 1 == d[v]) || ((type[v] & 1) && d[u] + 1 == f[v])) { Dinic.addEdge(u, v, 1, INF), mark[u] = true; type[u] |= 2; } } } //考虑同层转移 for (int k = i; k >= j; --k) { if (dict.count(f[ps[k].id])) mark[ps[k].id] = true, type[ps[k].id] |= 1; if (mark[ps[k].id] && (type[ps[k].id] & 2)) dict.insert(d[ps[k].id] - (k - j)); //因为只有非同层转移爬上去的点才能插入被同层转移 } dict.clear(); for (int k = j; k <= i; ++k) { if (dict.count(f[ps[k].id])) mark[ps[k].id] = true, type[ps[k].id] |= 1; if (mark[ps[k].id] && (type[ps[k].id] & 2)) dict.insert(d[ps[k].id] - (i - k)); } dict.clear(); } printf("%d\n", Dinic.minFlow(s, t)); } int main() { n = ReadInt() + 1; ori_ps[0] = ps[0] = point(0, 0, 0); for (int i = 1; i < n; ++i) ps[i].get(), ps[i].id = i, ori_ps[i] = ps[i]; process(); dp(); printSolution(); solve(); return 0; }
