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

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 ) (n1)(m1)(n1)(m1)个区域。不幸的是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≤20001 ≤ 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 A0ai​A。接下来m mm行第i ii行一个整数b i b_ibi​保证0 b i B 0 \lt b_i \lt B0bi​B。输出格式输出拆除栅栏的最小长度。答案需要用 64 位带符号整数存储。输入输出样例 #1输入 #115 15 5 2 2 5 10 6 4 11 3输出 #144C实现#includeiostream#includealgorithmusingnamespacestd;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)*(m1)y;}boolcmp(EDGE x,EDGE y){returnx.wy.w;}intfa[5000005];intFind(intx){if(fa[x]x)returnx;returnfa[x]Find(fa[x]);}longlongans;signedmain(){cinABnm;for(inti1;in;i)cina[i];a[n1]A;for(inti1;im;i)cinb[i];b[m1]B;sort(a1,an1);//数组并非有序sort(b1,bm1);for(intin1;i;i--)a[i]-a[i-1];//作差求出每段栅栏的长度for(intim1;i;i--)b[i]-b[i-1];for(inti1;in1;i){for(intj1;jm1;j){if(i1)add(f(i,j),f(i-1,j),b[j]);//连边if(j1)add(f(i,j),f(i,j-1),a[i]);}}for(inti1;i(n1)*(m1);i)fa[i]i;sort(edge1,edgetot1,cmp);intcnt(n1)*(m1);for(inti1;itot;i){intuedge[i].u,vedge[i].v,wedge[i].w;if(Find(u)!Find(v)){cnt--;answ;fa[Find(u)]Find(v);}}coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容