題意：給出二維平面的n個點坐標(biāo)，定義一種操作：若恰好三個點能形成一個矩形(當(dāng)然這個矩形會缺了一個點)，那么就在圖上添加這個缺的點，問在原圖上最多能進行幾次這樣的操作。

解法：這題想了挺久沒想到，一看題解發(fā)現(xiàn)z自己思路和正解完全不沾邊(尷尬)。解法參考https://www.cnblogs.com/zaq19970105/p/11108175.html這位大佬的。我們把x軸看作二分圖的左邊點，y軸看作二分圖右邊點，對于原圖上的點就向左邊點向右邊點連邊，即二分圖一條邊就是原圖一個點。然后我們先觀察四個點能構(gòu)成矩形有什么特點：如果在二分圖上左邊任意兩個點和任意右邊兩個點有4條連邊就是能構(gòu)成矩形，那么怎么才是缺一個點呢？基于上面就不難想了，就是左兩個點和右兩個點只有3條邊，那么缺的那一條邊就是缺的點。然后接下來這個發(fā)現(xiàn)就難一點了，就是如果左兩個點右兩個點至少有3條邊相連，那么這四個點就必須是連通的(而若只有兩條邊就不會)。那么按原圖在二分圖進行連邊之后就會出現(xiàn)一個個聯(lián)通塊，進行一次題目操作就會在聯(lián)通塊上加一條邊，直到加到不能加就是完全二分圖為止。那么答案就出來了：就是每個聯(lián)通塊完全圖邊數(shù)-原圖已有的邊數(shù) ，所有聯(lián)通塊加起來就是答案。

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=2e5+10; 4 typedef long long LL; 5 int n,X,Y; 6 vector<int> G[N],v; 7 bool vis[N]; 8 9 void dfs(int x,int dep) { 10 if (dep%2) X++; else Y++; 11 v.push_back(x); 12 vis[x]=1; 13 for (int i=0;i<G[x].size();i++) { 14 int t=G[x][i]; 15 if (vis[t]) continue; 16 dfs(t,dep+1); 17 } 18 } 19 20 int main() 21 { 22 cin>>n; 23 for (int i=1;i<=n;i++) { 24 int x,y; scanf("%d%d",&x,&y); 25 G[x].push_back(y+100000); 26 G[y+100000].push_back(x); 27 } 28 29 memset(vis,0,sizeof(vis)); 30 LL ans=0; 31 for (int i=1;i<=200000;i++) 32 if (G[i].size() && !vis[i]) { 33 X=0; Y=0; v.clear(); 34 dfs(i,1); 35 LL num=0; 36 for (int j=0;j<v.size();j++) num+=G[v[j]].size(); 37 ans+=(LL)X*Y-num/2; 38 } 39 cout<<ans<<endl; 40 return 0; 41 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/clno1/p/11224028.html

總結(jié)

以上是生活随笔為你收集整理的AtCoder Beginner Contest 131 F - Must Be Rectangular!的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。