当前位置：首页 > news >正文

打卡信奥刷题（3001）用C++实现信奥题 P6171 [USACO16FEB] Fenced In G

news 2026/3/26 20:17:41

P6171 [USACO16FEB] Fenced In G

题目背景

本题和白金组同名题目在题意上一致，唯一的不同是数据范围。

题目描述

Farmer John 意识到他的奶牛最近患上了一种恐惧症（害怕过于开阔的空间）。为了减少放牧的恐惧，FJ 决定在牧场中建一些水平和竖直方向的栅栏来将牧场分成若干个小区域。

整个牧场是一个矩形，两个角的坐标分别为( 0 , 0 ) (0,0)(0,0)和( A , B ) (A,B)(A,B)。FJ 在a 1 , … , a n a_1,\ldots ,a_na1,…,an这n nn个两两不同的位置建造了竖直方向的栅栏，每个栅栏从( a i , 0 ) (a_i,0)(ai,0)到( a i , B ) (a_i,B)(ai,B)；FJ 在b 1 , … , b m b_1,\ldots ,b_mb1,…,bm这m mm个两两不同的位置建造了水平方向的栅栏，每个栅栏从( 0 , b i ) (0,b_i)(0,bi)到( A , b i ) (A,b_i)(A,bi)。竖直方向的栅栏和水平方向的栅栏两两相交，将整个牧场分割成( n + 1 ) ( m + 1 ) (n+1)(m+1)(n+1)(m+1)个区域。

不幸的是，FJ 忘记了在栅栏上开门，奶牛都只能被困在一个个的小区域里！他想通过去掉一些栅栏来解决这个问题。他一次可以选择两个相邻的区域，将隔离这两个区域的栅栏去掉。FJ 的目标是让奶牛能够抵达牧场的任意一个地方。

这是一个例子：

+---+--+ | | | +---+--+ | | | | | | +---+--+

去掉一些栅栏后的效果是这样的：

+---+--+ | | +---+ + | | | | +---+--+

为了降低工程量，FJ 当然希望拆除的栅栏长度最短。

输入格式

第一行四个整数A , B , n , m A,B,n,mA,B,n,m，保证1 ≤ n , m ≤ 2000 1 \leq n,m \leq 20001≤n,m≤2000，1 ≤ A , B ≤ 10 9 1 \leq A,B \leq 10^91≤A,B≤109。

接下来n nn行，第i ii行一个整数a i a_iai，保证0 < a i < A 0 \lt a_i \lt A0<ai<A。

接下来m mm行，第i ii行一个整数b i b_ibi，保证0 < b i < B 0 \lt b_i \lt B0<bi<B。

输出格式

输出拆除栅栏的最小长度。答案需要用 64 位带符号整数存储。

输入输出样例 #1

输入 #1

15 15 5 2 2 5 10 6 4 11 3

输出 #1

C++实现

#include<iostream>#include<algorithm>usingnamespacestd;intA,B,n,m;inta[2005],b[2005];structEDGE{intu,v,w,nxt;}edge[9000005];inthead[5000005],tot;voidadd(intu,intv,intw){edge[++tot]={u,v,w,head[u]};head[u]=tot;}intf(intx,inty){//计算区域对应点的编号return(x-1)*(m+1)+y;}boolcmp(EDGE x,EDGE y){returnx.w<y.w;}intfa[5000005];intFind(intx){if(fa[x]==x)returnx;returnfa[x]=Find(fa[x]);}longlongans;signedmain(){cin>>A>>B>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];a[n+1]=A;for(inti=1;i<=m;i++)cin>>b[i];b[m+1]=B;sort(a+1,a+n+1);//数组并非有序sort(b+1,b+m+1);for(inti=n+1;i;i--)a[i]-=a[i-1];//作差求出每段栅栏的长度for(inti=m+1;i;i--)b[i]-=b[i-1];for(inti=1;i<=n+1;i++){for(intj=1;j<=m+1;j++){if(i>1)add(f(i,j),f(i-1,j),b[j]);//连边if(j>1)add(f(i,j),f(i,j-1),a[i]);}}for(inti=1;i<=(n+1)*(m+1);i++)fa[i]=i;sort(edge+1,edge+tot+1,cmp);intcnt=(n+1)*(m+1);for(inti=1;i<=tot;i++){intu=edge[i].u,v=edge[i].v,w=edge[i].w;if(Find(u)!=Find(v)){cnt--;ans+=w;fa[Find(u)]=Find(v);}}cout<<ans<<endl;return0;}