【洛谷2304_LOJ2134】[NOI2015]小园丁与老司机（动态规划_网络流）
2024-08-23 21:40:58
题目：
（LOJ 上每个测试点有部分分）
写了快一天 …… 好菜啊
分析：
毒瘤二合一题 ……
注意本题（及本文）使用 \(x\) 向右，\(y\) 向上的「数学坐标系」，而不是 \(x\) 向下，\(y\) 向右的所谓「OI 坐标系」。「同一行」指 \(y\) 相同，「同一列」指 \(x\) 相同。
老司机
注意，只能在 没有经过的 树下转向，并且每棵树只能访问一次。
第一反应是 \(f_{u}\) 表示从点 \(u\) （树 \(u\) ）出发能走到的最多的点数（不含本身），记忆化搜索，则答案就是 \(f_0\) （令 \((0,0)\) 为 \(0\) 号点）。然而，这样转移是有环的，因为同一行中互相可达。
那么就考虑逐行转移。先对于所有点 \(u\) 处理出所有不同行的可达的 \(v\) （即 \(u\) 与 \(v\) 的横坐标相等、横纵坐标之和相等或横纵坐标之差相等且 \(u\) 与 \(v\) 的连线上没有其他点）。计算 \(f(u)\) 时，先枚举它在同行走到了哪个点，再枚举它从那个点走到了上方的哪个点。设当前点是该行的第 \(p\) 个点，要走到同行的第 \(k\) 个点。若 \(p<k\) ，则最优策略是先走完左侧的所有点，再向右走到 \(k\) ，然后向上走；若 \(p=k\) ，则只能直接向上走；若 \(p>k\) ，则先走完右侧的所有点，再向左走到 \(k\) 。形式化地（其中 \(p_{i,j}\) 表示 \(y=i\) 的横坐标从小到大第 \(j\) 个点，标号从 \(0\) 开始。\(a_i\) 表示 \(y=i\) 的总点数）：
\[f_{p_{y,i}}=\max\begin{cases}
a_y-k-1\ (k<i且p_{y,k}无出边)\\
f_v+a_y-k\ (k<i且p_{y,k}到v有连边)\\
f_v+1\ (p_{y,i}到v有连边)\\
k\ (k>i且p_{y,k}无出边)\\
f_v+k+1\ (k>i且p_{y,i}到v有连边)\\
\end{cases}
\]
a_y-k-1\ (k<i且p_{y,k}无出边)\\
f_v+a_y-k\ (k<i且p_{y,k}到v有连边)\\
f_v+1\ (p_{y,i}到v有连边)\\
k\ (k>i且p_{y,k}无出边)\\
f_v+k+1\ (k>i且p_{y,i}到v有连边)\\
\end{cases}
\]
（注意要讨论边界情况。状态定义中不含 \(p_{y,i}\) 这点本身的贡献）
时间复杂度 \(O(nm)\) ，其中 \(m\) 表示每行最大的点数。题面上说 \(m\leq 1000\) 但是小恐龙说数据里有到 \(1600\) 多的？
至于输出方案，转移的时候记录一下转移时用的 \(k\) 是哪个，然后在 \(p_{y,k}\) 的出边中找哪个点的 \(f\) 值加上 \(a_y-k-1\) 之类的东西（视 \(k\) 和 \(i\) 的大小关系而定）等于当前点的 \(f\) 值，走过去就 OK 啦。
于是第一问就 愉快地 解决啦。
小园丁
首先用和输出方案类似的方法处理出哪些连边是可能存在于最优路径中的。然后考虑限制：
压路机可以从任意一棵树下出发，在任意一棵树下停止
压路机只能经过可能存在于最优路径中的边，每条边要被经过至少一次\
这不是 …… 网络流？？
每条边的权值是 \([1,+\infty)\) ，然后源点向所有点连 \([0,+\infty)\) ，所有点向汇点连 \([0,+\infty)\) ，然后就是一个上下界有源汇最小流板子了。（啥玩意？） 我是照着小恐龙的博客现学的。
为酒肉朋友打广告：有上下界的网络流/费用流 学习笔记 - Little Dino
代码：
写自闭了 ……
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <map>
#include <queue>
using namespace std;
namespace zyt
{
template<typename T>
inline bool read(T &x)
{
char c;
bool f = false;
x = 0;
do
c = getchar();
while (c != EOF && c != '-' && !isdigit(c));
if (c == EOF)
return false;
if (c == '-')
f = true, c = getchar();
do
x = x * 10 + c - '0', c = getchar();
while (isdigit(c));
if (f)
x = -x;
return true;
}
template<typename T>
inline void write(T x)
{
static char buf[20];
char *pos = buf;
if (x < 0)
putchar('-'), x = -x;
do
*pos++ = x % 10 + '0';
while (x /= 10);
while (pos > buf)
putchar(*--pos);
}
typedef pair<int, int> pii;
const int N = 5e4 + 10, M = 1e3 + 10, INF = 0x3f3f3f3f;
int n, X[N], Y[N], head[N], ecnt, ycnt;
pii pos[N], dp[N];
bool vis[N];
vector<int> id[N];
map<int, vector<int> > mp;
struct edge
{
int to, next;
}e[N * 3];
void add(const int a, const int b)
{
e[ecnt] = (edge){b, head[a]}, head[a] = ecnt++;
}
bool cmpx(const int a, const int b)
{
return X[a] < X[b];
}
void init()
{
static map<int, int> x, x_add_y, x_sub_y;
memset(head, -1, sizeof(int[n + 1]));
for (int i = 1; i <= n; i++)
mp[Y[i]].push_back(i);
for (auto it = mp.rbegin(); it != mp.rend(); it++)
{
sort(it->second.begin(), it->second.end(), cmpx);
id[++ycnt] = it->second;
for (auto itt = it->second.begin(); itt != it->second.end(); itt++)
{
int u = *itt;
pos[u] = pii(ycnt, itt - it->second.begin());
if (x.count(X[u]))
add(u, x[X[u]]);
x[X[u]] = u;
if (x_add_y.count(X[u] + Y[u]))
add(u, x_add_y[X[u] + Y[u]]);
x_add_y[X[u] + Y[u]] = u;
if (x_sub_y.count(X[u] - Y[u]))
add(u, x_sub_y[X[u] - Y[u]]);
x_sub_y[X[u] - Y[u]] = u;
}
}
}
template<typename T>
inline void get_max(T &a, const T b)
{
a = max(a, b);
}
int dfs(const int u)
{
int y = pos[u].first, p = pos[u].second;
if (vis[u])
return dp[u].first;
vis[u] = true;
dp[u] = pii(0, 0);
for (int k = 0; k < p; k++)
{
int now = id[y][k], res = 0;
for (int i = head[now]; ~i; i = e[i].next)
{
int v = e[i].to;
get_max(res, dfs(v));
}
get_max(dp[u], pii(res + id[y].size() - k - (head[now] == -1), now));
}
for (int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
get_max(dp[u], pii(dfs(v) + 1, u));
}
for (int k = p + 1; k < id[y].size(); k++)
{
int now = id[y][k], res = 0;
for (int i = head[now]; ~i; i = e[i].next)
{
int v = e[i].to;
get_max(res, dfs(v));
}
get_max(dp[u], pii(res + k + (head[now] != -1), now));
}
return dp[u].first;
}
void work1()
{
int ans = dfs(n);
write(ans), putchar('\n');
int tmp = n;
while (tmp)
{
if (tmp != n)
write(tmp), putchar(' ');
int y = pos[tmp].first, p = pos[tmp].second, nxt = dp[tmp].second, delta = 1, nxtt = 0;
if (!nxt)
break;
if (pos[nxt].second < p)
{
for (int i = p + 1; i < id[y].size(); i++)
write(id[y][i]), putchar(' '), ++delta;
for (int i = p - 1; i >= pos[nxt].second; i--)
write(id[y][i]), putchar(' '), ++delta;
}
else if (pos[nxt].second > p)
{
for (int i = p - 1; i >= 0; i--)
write(id[y][i]), putchar(' '), ++delta;
for (int i = p + 1; i <= pos[nxt].second; i++)
write(id[y][i]), putchar(' '), ++delta;
}
for (int i = head[nxt]; ~i; i = e[i].next)
{
int v = e[i].to;
if (dp[v].first + delta == dp[tmp].first)
{
nxtt = v;
break;
}
}
tmp = nxtt;
}
putchar('\n');
}
namespace Subtask2
{
int s, t, S, T, out[N];
namespace Dinic
{
struct edge
{
int to, w, next;
}e[N * 12];
int cur[N], dis[N], head[N], ecnt, s, t;
void add(const int a, const int b, const int c)
{
e[ecnt] = (edge){b, c, head[a]}, head[a] = ecnt++;
}
void addtw(const int a, const int b, const int c)
{
add(a, b, c), add(b, a, 0);
}
bool bfs()
{
memset(dis, -1, sizeof(int[T + 1]));
memcpy(cur, head, sizeof(int[T + 1]));
static queue<int> q;
q.push(s);
dis[s] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if (e[i].w && dis[v] == -1)
dis[v] = dis[u] + 1, q.push(v);
}
}
return dis[t] != -1;
}
int dfs(const int u, const int minn)
{
if (u == t || !minn)
return minn;
int used = 0;
for (int &i = cur[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if (e[i].w && dis[v] == dis[u] + 1)
{
int w = dfs(v, min(minn - used, e[i].w));
e[i].w -= w, e[i ^ 1].w += w, used += w;
if (used == minn)
break;
}
}
return used;
}
int work(const int _s, const int _t)
{
s = _s, t = _t;
int ans = 0;
while (bfs())
ans += dfs(s, INF);
return ans;
}
}
void work()
{
using Dinic::addtw;
static queue<int> q;
static bool vis[N], mark[N * 3];
s = n + 1, t = n + 2, S = n + 3, T = n + 4;
memset(Dinic::head, -1, sizeof(int[T + 1]));
for (int i = 1; i <= n; i++)
addtw(s, i, INF), addtw(i, t, INF);
q.push(n);
while (!q.empty())
{
int u = q.front();
int y = pos[u].first, p = pos[u].second;
q.pop();
for (int k = 0; k < p; k++)
{
int now = id[y][k], delta = id[y].size() - k;
for (int i = head[now]; ~i; i = e[i].next)
{
int v = e[i].to;
if (!mark[i] && dp[v].first + delta == dp[u].first)
{
++out[now], --out[v], addtw(now, v, INF), mark[i] = true;
if (!vis[v])
q.push(v), vis[v] = true;
}
}
}
for (int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if (!mark[i] && dp[v].first + 1 == dp[u].first)
{
++out[u], --out[v], addtw(u, v, INF), mark[i] = true;
if (!vis[v])
q.push(v), vis[v] = true;
}
}
for (int k = p + 1; k < id[y].size(); k++)
{
int now = id[y][k], delta = k + 1;
for (int i = head[now]; ~i; i = e[i].next)
{
int v = e[i].to;
if (!mark[i] && dp[v].first + delta == dp[u].first)
{
++out[now], --out[v], addtw(now, v, INF), mark[i] = true;
if (!vis[v])
q.push(v), vis[v] = true;
}
}
}
}
for (int i = 1; i <= n; i++)
if (out[i] < 0)
addtw(S, i, -out[i]);
else
addtw(i, T, out[i]);
addtw(t, s, INF);
Dinic::work(S, T);
int flow = Dinic::e[Dinic::ecnt - 1].w;
Dinic::e[Dinic::ecnt - 1].w = Dinic::e[Dinic::ecnt - 2].w = 0;
write(flow - Dinic::work(t, s));
}
}
int work()
{
read(n);
for (int i = 1; i <= n; i++)
read(X[i]), read(Y[i]);
++n, X[n] = Y[n] = 0;
init();
work1();
Subtask2::work();
return 0;
}
}
int main()
{
#ifdef BlueSpirit
freopen("2304.in", "r", stdin);
#endif
return zyt::work();
}
最新文章
- session失效后，登录页面嵌入iframe框架
- 在Eclipse中安装SVN客户端插件
- 有用的MySQL语句
- java mock
- ASP.NET-【缓存】-使用ASP.NET缓存
- git日常操作
- jquery操作iframe中的js函数
- 哈希，哈希表，哈希Map
- C# 超级简单的Telnet (TcpClient)客户端
- 每天一个小算法（4）----在O(1)时间删除指定结点
- http协议报头信息和主体鉴别
- Anaconda 安装概要
- void与void*详解
- Spring框架下的定时任务quartz框架的使用
- 在java项目中加入百度富文本编辑器
- Halcon一日一练：图像分辨率与像素
- css选择器优选级及匹配原理（转）
- AngularJS服务及注入--Provider
- docker端口映射启动报错Error response from daemon: driver failed programming external connectivity on endpoint jms_guacamole
- nginx负载均衡三：keepalive+nginx双机热备 和负载均衡