当前位置: 首页 > 工具软件 > Domination > 使用案例 >

[ARC122F]Domination

宦砚
2023-12-01

题目

传送门 to AtCoder

题目概要
n n n 个红色的石子,有 m m m 个蓝色的石子。你可以任意移动蓝色的石子,代价是曼哈顿距离。即,如果你从 ( x 0 , y 0 ) (x_0,y_0) (x0,y0) 移动到 ( x , y ) (x,y) (x,y),代价是 ∣ x − x 0 ∣ + ∣ y − y 0 ∣ |x-x_0|+|y-y_0| xx0+yy0

你的目标是,用最小的代价,使得每个红色石子的右上方都有至少 k k k 个蓝色的石子。石子的位置可以重叠,“右上方” 是闭区间,即, ( x , y ) (x,y) (x,y) ( x 0 , y 0 ) (x_0,y_0) (x0,y0) 的右上方,等价于 x 0 ≤ x x_0\le x x0x y 0 ≤ y y_0\le y y0y

数据范围与提示
k ≤ 10 k\le 10 k10,但是 n , m ≤ 1 0 5 n,m\le 10^5 n,m105

思路

宋队:  ⁣                                     ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ ⁣ j i a n g l y \!{\over\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\color{black}{j}\color{red}{iangly}} jiangly 连这道题都做不来,还挺一般的嘛。

其实用屁股想也知道,这种问题基本上就是图论了。当然 d p \tt dp dp 也是需要尝试一下的,只不过 i t    t u r n e d    o u t    d i f f i c u l t \rm it\;turned\;out\;difficult itturnedoutdifficult 罢了。

这个建图实在是太巧妙了!真的太巧妙了!只能说太巧妙了!我也不知道为什么要这么想。

首先考虑 k = 1 k=1 k=1 的时候,讨论单个红色石头。题目中要求移动蓝色的石头,但建图非要 各移动一半:把 r e d    s t o n e \rm red\;stone redstone 往下移动,然后把 b l u e    s t o n e \rm blue\;stone bluestone 往右移动。不妨把两个移动分解到坐标轴上,我们得到:

  • y y y 轴上,向下移动代价为 1 1 1,而向上移动代价为 0 0 0 。这里我们要从 R Y i RY_i RYi 移动到 B Y j BY_j BYj
  • x x x 轴上,向右移动代价为 1 1 1,而向左移动代价为 0 0 0 。这里我们要从 B X j BX_j BXj 移动到 R X i RX_i RXi
  • 显然二者之间需要一个桥梁:从 ( 0 , B Y j ) (0,BY_j) (0,BYj) 飞跃到 ( B X j , 0 ) (BX_j,0) (BXj,0) 的代价为 0 0 0
  • 另外注意一点:原点处不能转弯。我一开始以为原点可以转弯,然后就不能理解……

在这个图中, ( 0 , R Y i ) (0,RY_i) (0,RYi) ( R X i , 0 ) (RX_i,0) (RXi,0) 的最短路就是答案。

这是一个红色石头的情况。考虑多个红色石头。显然有包含关系的可以直接去掉,所以剩下的红色石头满足 R X RX RX 单增且 R Y RY RY 单减。那么,想要用一个蓝色石头同时满足 [ l , r ] [l,r] [l,r] 之间的红色石头,其实就是要 B X j ′ ≥ R X r BX'_j\ge RX_r BXjRXr B Y j ′ ≥ R Y l BY'_j\ge RY_l BYjRYl 。相当于一个位于 ( R X r , R Y l ) (RX_r,RY_l) (RXr,RYl) 的红色石头嘛!

于是类似的,我们知道,从 ( 0 , R Y l ) (0,RY_l) (0,RYl) 走到 ( R X r , 0 ) (RX_r,0) (RXr,0) 的最短路就是答案。

可是我们有不只一个蓝色石头,可以分别解决一些区间。怎么将其合并呢?还是像上面一样,利用 0 0 0 代价的桥梁。第一个蓝色石头从 ( 0 , R Y 1 ) (0,RY_1) (0,RY1) 走到 ( R X t , 0 ) (RX_t,0) (RXt,0),搞定了 [ 1 , t ] [1,t] [1,t] 的红色石头;第二个蓝色石头从 ( 0 , R Y t + 1 ) (0,RY_{t+1}) (0,RYt+1) 走到 ( R X n , 0 ) (RX_n,0) (RXn,0),搞定了 [ t + 1 , n ] [t+1,n] [t+1,n] 的红色石头。

  • 那么中间桥梁就是 ( R X t , 0 ) (RX_t,0) (RXt,0) 走到 ( 0 , R Y t + 1 ) (0,RY_{t+1}) (0,RYt+1) 呗。
  • 此时 ( 0 , R Y 1 ) (0,RY_1) (0,RY1) ( R X n , 0 ) (RX_n,0) (RXn,0) 的最短路就是答案。

然后能不能推广到 k k k 为任意值呢?完全可以嘛。只需要一个流量为 k k k 的流。相当于我们需要 k k k 组蓝色的石子,每一组蓝色的石子都能让所有红色的石子满足 k = 1 k=1 k=1 的情况。因为每个蓝色石子的管控范围是一个区间,很容易证明这与原问题等价。

蓝色的石头只能用一次,恰好就是容量 1 1 1 呗。所以真的变成网络流了。时间复杂度 O [ k ( n + m ) log ⁡ ( n + m ) ] \mathcal O[k(n+m)\log(n+m)] O[k(n+m)log(n+m)]

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long int_;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MaxN = 500005;
const int_ long_infty = (1ll<<60)-1;
const int infty = (1<<30)-1;

struct Edge{
	int to, nxt, val, cost;
	Edge(){} // val is capacity
	Edge(int T,int N,int V,int C){
		to = T, nxt = N;
		val = V, cost = C;
	}
};
Edge e[MaxN*12];
int head[MaxN], cntEdge;
void addEdge(int a,int b,int c,int d){
	e[cntEdge] = Edge(b,head[a],c,d);
	head[a] = cntEdge ++;
	e[cntEdge] = Edge(a,head[b],0,-d);
	head[b] = cntEdge ++;
}

int_ dis[MaxN], h[MaxN];
int pre[MaxN];
struct PII{
	int_ dis; int id;
	PII(int_ D,int I):dis(D),id(I){}
	bool operator < (const PII &t) const {
		return dis > t.dis;
	}
};
priority_queue<PII> q;
void dijkstra(int from,int n){
	fill(dis+1,dis+n+1,long_infty);
	q.push(PII(dis[from]=0,from));
	while(!q.empty()){
		int x = q.top().id;
		if(dis[x] < q.top().dis){
			q.pop(); continue;
		} else q.pop();
		for(int i=head[x]; ~i; i=e[i].nxt){
			int y = e[i].to, zxy = e[i].cost+dis[x];
			if(e[i].val && dis[y] > zxy+h[x]-h[y]){
				dis[y] = zxy+h[x]-h[y];
				pre[y] = i;
				q.push(PII(dis[y],y));
			}
		}
	}
}
int_ flow(int from,int to,int n){
	dijkstra(from,n);
	int_ res = dis[to]+h[to];
	for(int x=to,y; x!=from; x=y){
		y = e[pre[x]^1].to;
		-- e[pre[x]].val;
		++ e[pre[x]^1].val;
	}
	rep(i,1,n) h[i] += dis[i];
	return res;
}

struct Point{
	int x, y;
	bool operator < (const Point &t) const {
		if(x != t.x) return x < t.x;
		return y < t.y;
	}
};
Point p[MaxN];
int tmpx[MaxN], tmpy[MaxN];

int main(){
	memset(head,-1,sizeof(head));
	int n = readint(), m = readint();
	int k = readint();
	for(int i=1; i<=n+m; ++i){
		tmpx[i] = p[i].x = readint();
		tmpy[i] = p[i].y = readint();
	}
	sort(tmpx+1,tmpx+n+m+1);
	sort(tmpy+1,tmpy+n+m+1);
	int X = unique(tmpx+1,tmpx+n+m+1)-tmpx-1;
	int Y = unique(tmpy+1,tmpy+n+m+1)-tmpy-1;
	rep(i,1,X-1){
		addEdge(i,i+1,infty,tmpx[i+1]-tmpx[i]);
		addEdge(i+1,i,infty,0); // for free
	}
	rep(i,1,Y-1){
		addEdge(X+i+1,X+i,infty,tmpy[i+1]-tmpy[i]);
		addEdge(X+i,X+i+1,infty,0); // no cost
	}
	sort(p+1,p+n+1); // all red stones
	int deprive = 0;
	for(int i=n-1; i-deprive>=1; --i){
		p[i] = p[i-deprive]; // shift
		if(p[i].y <= p[i+1].y)
			++ deprive, ++ i;
	}
	rep(i,1,n+m){
		p[i].x = lower_bound(tmpx+1,tmpx+X+1,p[i].x)-tmpx;
		p[i].y = lower_bound(tmpy+1,tmpy+Y+1,p[i].y)-tmpy;
	}
	for(int i=deprive+2; i<=n; ++i)
		addEdge(p[i-1].x,X+p[i].y,infty,0);
	for(int i=n+1; i<=n+m; ++i)
		addEdge(X+p[i].y,p[i].x,1,0); // capacity = 1
	long long ans = 0;
	for(int i=1; i<=k; ++i)
		ans += flow(X+p[deprive+1].y,p[n].x,X+Y);
	printf("%lld\n",ans);
	return 0;
}
 类似资料:

相关阅读

相关文章

相关问答