排位賽2-Fence Planning

題目

Farmer John’s N cows, conveniently numbered 1…N (2≤N≤105), have a complex social structure revolving around “moo networks” — smaller groups of cows that communicate within their group but not with other groups. Each cow is situated at a distinct (x,y) location on the 2D map of the farm, and we know that M pairs of cows (1≤M<105) moo at each-other. Two cows that moo at each-other belong to the same moo network.

In an effort to update his farm, Farmer John wants to build a rectangular fence, with its edges parallel to the x and y axes. Farmer John wants to make sure that at least one moo network is completely enclosed by the fence (cows on the boundary of the rectangle count as being enclosed). Please help Farmer John determine the smallest possible perimeter of a fence that satisfies this requirement. It is possible for this fence to have zero width or zero height.

題意

在二維網格上有n頭牛，他們之間有n對關系，現在需要建造柵欄，建造得柵欄一定要把有聯系的牛都圍起來，求最小面積的柵欄面積是多少。

解法

先用并查集將所有牛分好類，然后直接求每一個關系圈的牛所需要的柵欄面積即可。

代碼：

#include <stdio.h> #include <cstring> #include <algorithm> #include <iostream> #include <math.h> using namespace std; const int maxn=200010; int n,m,xx,yy,ans,father[maxn],max_x[maxn],min_x[maxn],max_y[maxn],min_y[maxn],x[maxn],y[maxn];int getfather(int x) {if (father[x]!=x) father[x]=getfather(father[x]);return father[x]; }int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);for (int i=1;i<=n;i++) {father[i]=i;max_x[i]=-1;min_x[i]=100000010;max_y[i]=-1;min_y[i]=100000010;}for (int i=1;i<=m;i++) {scanf("%d%d",&xx,&yy);int fax=getfather(xx);int fay=getfather(yy);if (fax==fay) continue;father[fax]=fay;}for (int i=1;i<=n;i++) {father[i]=getfather(father[i]);int fa=father[i];max_x[fa]=max(max_x[fa],x[i]);min_x[fa]=min(min_x[fa],x[i]);max_y[fa]=max(max_y[fa],y[i]);min_y[fa]=min(min_y[fa],y[i]);}ans=-1;for (int i=1;i<=n;i++) if (father[i]==i) {if (ans==-1) ans=(max_x[i]-min_x[i]+max_y[i]-min_y[i])*2; else ans=min(ans,(max_x[i]-min_x[i]+max_y[i]-min_y[i])*2);}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的排位赛2-Fence Planning的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。