差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:arc_122 [2021/06/16 20:15]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:arc_122 [2021/07/02 17:29] (当前版本)
jxm2001
@@ 行 238: / 行 238: @@
 	_for(i,0,n)
 	space(a[i]);
+	return 0;
+}
+</code>
+</hidden>
+===== F - Domination =====
+==== 题意 ====
+二维平面给定 $n$ 个红点和 $m$ 个蓝点，可以任意次移动某个蓝点，费用为曼哈顿距离。
+问满足下述情况的最小费用：
+对每个红点 $(x_r,y_r)$ 至少有 $k$ 个蓝点 $(x_b,r_b)$ 满足 $x_b\ge x_r,y_b\ge y_r$。
+==== 题解 ====
+定义如果 $x_b\ge x_r,y_b\ge y_r$，则称 $(x_b,y_b)$ 覆盖 $(x_r,y_r)$。首先考虑 $k=1$ 且只有一个红点 $(x_r,y_r)$ 和多个蓝点的情况。
+重新建图，图中只有 $X$ 轴和 $Y$ 轴上的点，且 $X$ 轴的 $(0,0)$ 和 $Y$ 轴的 $(0,0)$ 不是同一个点。
+$(x,0)\to (x+1,0)$ 费用为 $1$，$(x+1,0)\to (x,0)$ 费用为 $0$。 $(0,y)\to (0,y+1)$ 费用为 $0$，$(0,y+1)\to (0,y)$ 费用为 $1$。
+对每个蓝点，代表一条从 $(0,y_b)$ 连向 $(x_b,0)$ 的费用为 $0$ 的边。
+于是红点被该蓝点覆盖的费用恰好为路径 $(0,y_r)\to (0,y_b)\to (x_b,0)\to (x_r,0)$ 的费用。
+所以该情况下的最小费用为 $(0,y_r)\to (x_r,0)$ 的最短路。
+接下来考虑 $k=1$ 且有多个红点 $(x_r,y_r)$ 和多个蓝点的情况。
+对某个红点，如果被另一个红点，显然可以删除这个红点。
+将红点按 $X$ 坐标从小到大排序，不难发现红点 $Y$ 坐标递减。记排序后第 $i$ 个红点坐标为 $(x_i,y_i)$。
+对每个蓝点，不难发现覆盖区域恰好是下标连续的一段红点，于是蓝点的覆盖下标恰好为 $[1,k_1],[k_1+1,k_2]\cdots [k_m+1,n]$。
+添加连边 $(x_i,0)\to (0,y_{i+1})$，表示前 $i$ 个红点被前 $t$ 个蓝点覆盖，第 $i+1$ 个红点属于第 $t+1$ 个蓝点的情况。
+接下来求 $(0,y_1)\to (x_n,0)$ 的最短路即可。
+最后考虑 $k\neq 1$ 且有多个红点 $(x_r,y_r)$ 和多个蓝点的情况。
+每个蓝点对每个红点在统计覆盖时贡献最多为 $1$，于是将从 $(0,y_b)$ 连向 $(x_b,0)$ 的边的容量设置成 $1$。
+然后跑 $s\to (0,y_1)\to (x_n,0)\to t$ 的流量为 $k$ 的最小费用流即可。
+相当于跑 $k$ 次最短路，费用流中的 $\text{spfa}$ 利用优先队列优化据说可以做到 $O(kn\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXM=10*MAXN,inf=1e9;
+struct Edge{
+	int to,cap,w,next;
+	Edge(int to=0,int cap=0,int w=0,int next=0){
+		this->to=to;
+		this->cap=cap;
+		this->w=w;
+		this->next=next;
+	}
+}edge[MAXM<<1];
+int head[MAXN<<2],edge_cnt;
+void Clear(){mem(head,-1);edge_cnt=0;}
+void Insert(int u,int v,int w,int c){
+	edge[edge_cnt]=Edge(v,c,w,head[u]);
+	head[u]=edge_cnt++;
+	edge[edge_cnt]=Edge(u,0,-w,head[v]);
+	head[v]=edge_cnt++;
+}
+namespace EK{
+	int a[MAXN<<2],p[MAXN<<2];
+	LL dis[MAXN<<2];
+	void MCMF(int s,int t,int &flow,LL &cost){
+		flow=0,cost=0;
+		while(true){
+			mem(a,0);
+			_for(i,0,MAXN<<2)dis[i]=1e18;
+			priority_queue<pair<LL,int> > q;
+			a[s]=inf,dis[s]=0;
+			q.push(make_pair(0,s));
+			while(!q.empty()){
+				int u=q.top().second;
+				LL w=q.top().first;
+				q.pop();
+				if(w!=-dis[u])continue;
+				for(int i=head[u];~i;i=edge[i].next){
+					int v=edge[i].to;
+					if(edge[i].cap&&dis[u]+edge[i].w<dis[v]){
+						p[v]=i;
+						dis[v]=dis[u]+edge[i].w;
+						a[v]=min(a[u],edge[i].cap);
+						q.push(make_pair(-dis[v],v));
+					}
+				}
+			}
+			if(!a[t])
+			return;
+			for(int i=t;i!=s;i=edge[p[i]^1].to){
+				edge[p[i]].cap-=a[t];
+				edge[p[i]^1].cap+=a[t];
+			}
+			flow+=a[t];
+			cost+=a[t]*dis[t];
+		}
+	}
+};
+struct Node{
+	int x,y;
+	bool operator < (const Node &b)const{
+		return x<b.x||(x==b.x&&y<b.y);
+	}
+}node[MAXN],st[MAXN];
+int xx[MAXN<<1],yy[MAXN<<1];
+int main()
+{
+	int n=read_int(),m=read_int(),k=read_int();
+	Clear();
+	_for(i,0,n){
+		node[i].x=read_int();
+		node[i].y=read_int();
+	}
+	sort(node,node+n);
+	int pos=0;
+	_for(i,0,n){
+		while(pos&&st[pos].y<=node[i].y)pos--;
+		st[++pos]=node[i];
+	}
+	int cnt=0;
+	_rep(i,1,pos){
+		xx[cnt]=st[i].x;
+		yy[cnt++]=st[i].y;
+	}
+	_for(i,0,m){
+		node[i].x=read_int();
+		node[i].y=read_int();
+		xx[cnt]=node[i].x;
+		yy[cnt++]=node[i].y;
+	}
+	sort(xx,xx+cnt);
+	int cntx=unique(xx,xx+cnt)-xx;
+	sort(yy,yy+cnt);
+	int cnty=unique(yy,yy+cnt)-yy;
+	_for(i,1,cntx){
+		Insert(i-1,i,xx[i]-xx[i-1],inf);
+		Insert(i,i-1,0,inf);
+	}
+	_for(i,1,cnty){
+		Insert(i-1+cntx,i+cntx,0,inf);
+		Insert(i+cntx,i-1+cntx,yy[i]-yy[i-1],inf);
+	}
+	_rep(i,1,pos){
+		int u=lower_bound(xx,xx+cntx,st[i-1].x)-xx;
+		int v=lower_bound(yy,yy+cnty,st[i].y)-yy+cntx;
+		Insert(u,v,0,inf);
+	}
+	_for(i,0,m){
+		int u=lower_bound(yy,yy+cnty,node[i].y)-yy+cntx;
+		int v=lower_bound(xx,xx+cntx,node[i].x)-xx;
+		Insert(u,v,0,1);
+	}
+	int s=cntx+cnty,t=s+1;
+	Insert(s,lower_bound(yy,yy+cnty,st[1].y)-yy+cntx,0,k);
+	Insert(lower_bound(xx,xx+cntx,st[pos].x)-xx,t,0,k);
+	int flow;
+	LL cost;
+	EK::MCMF(s,t,flow,cost);
+	enter(cost);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具