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

打卡信奥刷题（3176）用C++实现信奥题 P7991 [USACO21DEC] Connecting Two Barns S

news 2026/4/27 13:50:40

P7991 [USACO21DEC] Connecting Two Barns S

题目描述

Farmer John 的农场由NNN块田地（1≤N≤1051 \leq N \leq 10^51≤N≤105）组成，编号为1…N1 \ldots N1…N。在这些田地之间有MMM条双向道路（0≤M≤1050 \leq M \leq 10^50≤M≤105），每条道路连接两块田地。

农场有两个牛棚，一个在田地 1 中，另一个在田地NNN中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素，在田地iii和jjj之间建造新道路的花费是(i−j)2(i-j)^2(i−j)2。

请帮助 Farmer John 求出使得牛棚111和NNN可以相互到达所需要的最小花费。

输入格式

每个测试用例的输入包含TTT个子测试用例（1≤T≤201\le T\le 201≤T≤20），所有子测试用例必须全部回答正确才能通过整个测试用例。

输入的第一行包含TTT，之后是TTT个子测试用例。

每个子测试用例的第一行包含两个整数NNN和MMM。以下MMM行，每行包含两个整数iii和jjj，表示一条连接两个不同田地iii和jjj的道路。输入保证任何两个田地之间至多只有一条道路，并且所有子测试用例的N+MN+MN+M之和不超过5⋅1055 \cdot 10^55⋅105。

输出格式

输出TTT行。第iii行包含一个整数，为第iii个子测试用例的最小花费。

输入输出样例 #1

输入 #1

2 5 2 1 2 4 5 5 3 1 2 2 3 4 5

输出 #1

2 1

说明/提示

【样例解释】

第一个子测试用例中，最优的方式是用一条道路连接田地 2 和 3，用一条道路连接田地 3 和 4。
第二个子测试用例中，最优的方式是用一条道路连接田地 3 和 4。不需要第二条道路。

【数据范围】

测试点 2 满足N≤20N \le 20N≤20。
测试点 3-5 满足N≤103N \le 10^3N≤103。
测试点 6-10 没有额外限制。

C++实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e5+5;intt,n,m,u,v,fa[maxn];ll ans;vector<int>g[maxn];llsquare(intx){return(ll)x*x;}intfind(intx){if(x==fa[x])returnx;returnfa[x]=find(fa[x]);}lldis(intx,inty){ll res=1e18;inta,b;for(inti=0;i<g[x].size();i++){a=g[x][i],b=lower_bound(g[y].begin(),g[y].end(),a)-g[y].begin();//二分if(b)res=min(res,square(a-g[y][b-1]));//比a小里最接近a的if(b<g[y].size())res=min(res,square(a-g[y][b]));//比a大里最接近a的}returnres;}intmain(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){fa[i]=i;g[i].clear();}//初始化for(inti=1;i<=m;i++){scanf("%d%d",&u,&v);fa[find(u)]=find(v);}for(inti=1;i<=n;i++)g[find(i)].push_back(i);u=fa[1],v=fa[n],ans=dis(u,v);//1与n直接相连for(inti=1;i<=n;i++){if(fa[i]==u||fa[i]==v||fa[i]!=i)continue;ans=min(ans,dis(i,u)+dis(i,v));//找到某个点与1和n相连}printf("%lld\n",ans);}return0;}