rvalue's blog
文章 标签 分类 个人 About Friends
rvalue's blog

目录

[LOJ 2134][UOJ 132][BZOJ 4200][NOI 2015]小园丁与老司机

rvalue 收录于 cnblogs 题解
   约 1796 字   预计阅读 4 分钟 
迁移提示
本文迁移自博客园, 原文链接

[LOJ 2134][UOJ 132][BZOJ 4200][NOI 2015]小园丁与老司机

题意

给定平面上的 $n$ 个整点 $(x_i,y_i)$, 一共有两个问题.

第一个问题是从原点 $(0,0)$ 出发, 在只能向←↖↑↗→五个方向中有未到达的点的方向走且在没有到达一个点的时候不能中途转弯的情况下最多能到达的点数, 并输出一种可行方案.

第二个问题是如果用若干可以从任意点出发但是只能向↖↑↗方向沿着所有可能出现在最优解的直线上走的压路机将所有可能出现在最优解上的边都走过至少一遍所需要的最少的压路机数量.

$n\le 50000,|x_i|\le 10^9,0<y_i\le 10^9$

题解

农业题真tm劲啊

第一个问题相当于一个有特殊限制的分层图最长路.

显然走的时候 $y$ 值是单调不降的, 我们可以从小到大枚举 $y$ 坐标分层计算.

同一层的时候假设在 $s$ 处进入, 从 $t$ 处离开, 那么最优策略一定是先走到这一层中对 $t$ 的对侧端点然后再回来. 我们设 $f^{[1]}_i$ 为从原点走到 $i$ 的最长路, $f^{[2]}_i$ 为上一层中可以走到点 $i$ 的点中最大的 $f^{[1]}$, 即进入当前层之前的最长路.

因为↖↑↗三个方向能移动到的位置分别保持 $x+y$, $x$, $x-y$ 相等, 于是可以全局维护一个哈希表或者 map 来维护 $f^{[2]}_i$. 如果以前没有出现过相等位置则贡献为 $-\infty$. 原点的贡献为 $0$.

从 $f^{[2]}$ 计算 $f^{[1]}$ 则可以分类讨论, $s=t$ 时是平凡情况, 注意这里到达后这个点会变成已到达的, 如果要访问同一层的其他点就会回不来, 于是这里直接等于 $f^{[2]}_i+1$. 剩下的情况一个是 $s<t$, 一个是 $s>t$.

$s<t$ 的时候可以访问到 $t$ 左侧的所有点, $s>t$ 的时候可以访问到 $t$ 右侧的所有点, 显然这个贡献和 $s$ 无关, 正反扫一遍记录一下前后缀最大的 $f^{[2]}_i$ 就好了.

以上贡献的时候都需要维护一个 pair, 第一关键字是DP值, 第二关键字是来源. 用 pair 可以节省额外的记录方案代码. 注意 $f^{[1]}_i$ 的来源记录的是同层的 $s$ 的位置, $f^{[2]}_i$ 的来源记录的是上一层的 $t$ 的位置.

输出方案的时候处理一下同一层的特判一下 $s=t$ 的情况第一个问题就做完了.

第二个问题依然比较恶心

下界最小流的模型很显然就不说了. 关键在于把这个图建出来. 因为它问的是所有可能出现在最优解的直线.

如果 $u$ 沿↖↑↗三个方向可以到达 $v$, 那么只要原点到 $u$ 的最长路和 $v$ 出发的最长路之和与第一问的答案相等就可以出现在最优解上. 那么就需要计算出从某个点出发的最长路的长度.

这个DP和第一问类似, 不再赘述. 不过这次可以在任意位置结束, 所以没有后继的时候贡献是 $0$ 而不是 $-\infty$.

最后注意一下不要写假Dinic…这题数据范围比较大, 假复杂度的Dinic很容易被卡…我猜Po姐就是因为写了假Dinic才没有阿克Day2的然而神仙Po姐实际上写了个费用流

参考代码

一杯茶, 一包烟, 一个破题调一天

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311

#include <bits/stdc++.h>

const int MAXV=50010;
const int MAXN=50010;
const int MAXE=1e7+10;
const int INF=0x7FFFFFFF;
typedef std::pair<int,int> Pair;

struct Edge{
	int from;
	int to;
	int flow;
	bool blk;
	Edge* rev;
	Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* cur[MAXV];
Edge* top=E;

int n;
int ycnt;
int s[MAXN];
Pair a[MAXN];
int id[MAXN];
int bk1[MAXN];
int bk2[MAXN];
Pair fw1[MAXN];
Pair fw2[MAXN];
int depth[MAXV];
std::map<int,int> bkX;
std::map<int,int> bkN;  // x+y fixed
std::map<int,int> bkZ;  // x-y fixed
std::map<int,Pair> fwX;
std::map<int,Pair> fwN; // x+y fixed
std::map<int,Pair> fwZ; // x-y fixed
std::vector<Pair> pos[MAXN];
std::pair<Pair,int> P[MAXN];

int ReadInt();
int GetB(int);
Pair GetF(int);
bool BFS(int,int);
int Dinic(int,int);
int DFS(int,int,int);
void UpdateF(int,int);
void UpdateB(int,int);
Edge* Insert(int,int,int);

int main(){
	n=ReadInt();
	for(int i=1;i<=n;i++){
		a[i].first=P[i].first.first=ReadInt();
		s[i]=a[i].second=P[i].first.second=ReadInt();
		P[i].second=i;
	}
	std::sort(s+1,s+n+1);
	std::sort(P+1,P+n+1);
	ycnt=std::unique(s+1,s+n+1)-(s+1);
	for(int i=1;i<=n;i++)
		pos[std::lower_bound(s+1,s+ycnt+1,P[i].first.second)-s].emplace_back(P[i].first.first,P[i].second);
	pos[0].emplace_back(0,0);
	UpdateF(0,0);
	Pair ans;
	for(int i=1;i<=ycnt;i++){
		for(size_t j=0;j<pos[i].size();j++){
			int x=pos[i][j].second;
			auto p=GetF(x);
			fw2[x]=p;
			fw1[x]=Pair(p.first+1,x);
		}
		auto maxf=Pair(INT_MIN,0);
		for(size_t j=0;j<pos[i].size();j++){
			int p=pos[i][j].second;
			id[p]=j;
			fw1[p]=std::max(fw1[p],Pair(maxf.first+j+1,maxf.second));
			if(fw2[p].first>=0)
				maxf=std::max(maxf,Pair(fw2[p].first,p));
		}
		maxf=Pair(INT_MIN,0);
		for(size_t j=pos[i].size()-1;j<pos[i].size();j--){
			int p=pos[i][j].second;
			fw1[p]=std::max(fw1[p],Pair(maxf.first+(pos[i].size()-j),maxf.second));
			if(fw2[p].first>=0)
				maxf=std::max(maxf,Pair(fw2[p].first,p));
			UpdateF(p,fw1[p].first);
			ans=std::max(ans,Pair(fw1[p].first,p));
		}
	}
	int bkans=0;
	for(int i=ycnt;i>=1;i--){
		for(size_t j=0;j<pos[i].size();j++){
			int x=pos[i][j].second;
			bk2[x]=GetB(x);
			bk1[x]=bk2[x]+1;
		}
		int maxb=0;
		for(size_t j=0;j<pos[i].size();j++){
			int p=pos[i][j].second;
			bk1[p]=std::max(bk1[p],maxb);
			maxb=std::max(maxb,int(bk2[p]+(pos[i].size()-j)));
		}
		maxb=0;
		for(size_t j=pos[i].size()-1;j<pos[i].size();j--){
			int p=pos[i][j].second;
			bk1[p]=std::max(bk1[p],maxb);
			maxb=std::max(maxb,int(bk2[p]+j+1));
			UpdateB(p,bk1[p]);
			bkans=std::max(bkans,bk1[p]);
		}
	}
	printf("%d\n",ans.first);
	std::vector<int> sol;
	for(int cur=ans.second;cur!=0;){
		sol.push_back(cur);
		int i=std::lower_bound(s+1,s+ycnt+1,a[cur].second)-s;
		if(fw1[cur].second!=cur){
			int next=fw1[cur].second;
			if(id[next]<id[cur]){
				for(int j=id[cur]-1;j>id[next];j--)
					sol.push_back(pos[i][j].second);
				for(int j=0;j<=id[next];j++)
					sol.push_back(pos[i][j].second);
			}
			else{
				for(int j=id[cur]+1;j<id[next];j++)
					sol.push_back(pos[i][j].second);
				for(int j=pos[i].size()-1;j>=id[next];j--)
					sol.push_back(pos[i][j].second);
			}
			cur=fw1[cur].second;
		}
		cur=fw2[cur].second;
	}
	for(int i=ans.first-1;i>=0;i--)
		printf("%d%c",sol[i]," \n"[i==0]);
	bkX.clear();
	bkN.clear();
	bkZ.clear();
	int ss=n+1,tt=n+2,s=n+3,t=n+4;
	Edge* Ex;
	std::vector<Edge*> aux;
	aux.push_back(Ex=Insert(t,s,INF));
	for(int i=0;i<=n;i++){
		Insert(s,i,INF);
		Insert(i,t,INF);
	}
	auto check=[=,&aux](int r,int k){
		if(fw1[r].first+bk1[k]==ans.first){
			Insert(r,k,INF);
			aux.push_back(Insert(ss,k,1));
			aux.push_back(Insert(r,tt,1));
		}
	};
	for(int i=ycnt;i>=0;i--){
		for(auto p:pos[i]){
			int x,y,r=p.second;
			std::tie(x,y)=a[r];
			if(bkX.count(x))
				check(r,bkX[x]);
			if(bkN.count(x+y))
				check(r,bkN[x+y]);
			if(bkZ.count(x-y))
				check(r,bkZ[x-y]);
			bkX[x]=r;
			bkN[x+y]=r;
			bkZ[x-y]=r;
		}
	}
	Dinic(ss,tt);
	for(auto p:aux)
		p->blk=p->rev->blk=true;
	int flow=Ex->rev->flow;
	flow-=Dinic(t,s);
	printf("%d\n",flow);
	return 0;
}

int GetB(int i){
	int ans=0;
	int x=a[i].first;
	int y=a[i].second;
	if(bkX.count(x))
		ans=std::max(ans,bkX[x]);
	if(bkN.count(x+y))
		ans=std::max(ans,bkN[x+y]);
	if(bkZ.count(x-y))
		ans=std::max(ans,bkZ[x-y]);
	return ans;
}

void UpdateB(int i,int d){
	if(d<0)
		return;
	int x=a[i].first;
	int y=a[i].second;
	auto f=[](int& x,int d){x=std::max(x,d);};
	f(bkX[x],d);
	f(bkN[x+y],d);
	f(bkZ[x-y],d);
}

Pair GetF(int i){
	int x=a[i].first;
	int y=a[i].second;
	Pair ans(INT_MIN,0);
	if(fwX.count(x))
		ans=std::max(ans,fwX[x]);
	if(fwN.count(x+y))
		ans=std::max(ans,fwN[x+y]);
	if(fwZ.count(x-y))
		ans=std::max(ans,fwZ[x-y]);
	return ans;
}

void UpdateF(int i,int d){
	if(d<0)
		return;
	int x=a[i].first;
	int y=a[i].second;
	auto p=Pair(d,i);
	auto f=[](Pair& x,Pair d){x=std::max(x,d);};
	f(fwX[x],p);
	f(fwN[x+y],p);
	f(fwZ[x-y],p);
}

int Dinic(int s,int t){
	int ans=0;
	while(BFS(s,t))
		ans+=DFS(s,INF,t);
	return ans;
}

bool BFS(int s,int t){
	memset(depth,0,sizeof(depth));
	std::queue<int> q;
	cur[s]=head[s];
	depth[s]=1;
	q.push(s);
	while(!q.empty()){
		s=q.front();
		q.pop();
		for(Edge* i=head[s];i!=NULL;i=i->next){
			if(!i->blk&&i->flow>0&&depth[i->to]==0){
				depth[i->to]=depth[s]+1;
				cur[i->to]=head[i->to];
				if(i->to==t)
					return true;
				q.push(i->to);
			}
		}
	}
	return false;
}

int DFS(int s,int flow,int t){
	if(s==t||flow<=0)
		return flow;
	int rest=flow;
	for(Edge*& i=cur[s];i!=NULL;i=i->next){
		if(!i->blk&&i->flow>0&&depth[i->to]==depth[s]+1){
			int tmp=DFS(i->to,std::min(rest,i->flow),t);
			if(tmp<=0)
				depth[i->to]=0;
			rest-=tmp;
			i->flow-=tmp;
			i->rev->flow+=tmp;
			if(rest<=0)
				break;
		}
	}
	return flow-rest;
}

inline Edge* Insert(int from,int to,int flow){
	Edge* ret=top;
	top->from=from;
	top->to=to;
	top->flow=flow;
	top->blk=false;
	top->rev=top+1;
	top->next=head[from];
	head[from]=top++;

	top->from=to;
	top->to=from;
	top->flow=0;
	top->blk=false;
	top->rev=top-1;
	top->next=head[to];
	head[to]=top++;
	return ret;
}

inline int ReadInt(){
	int x=0;
	int sgn=1;
	register char ch=getchar();
	while(!isdigit(ch)){
		sgn=(ch=='-'?-sgn:sgn);
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*sgn;
}

https://pic.rvalue.moe/2021/08/02/fb9f3292c0a4d.png

更新于 2019-06-15
阅读原始文档
 DP, 网络流
返回 | 主页