學(xué)到了很多。

我們分步走。

首先在做這道題前先觀察到幾個(gè)小性質(zhì)：

1. 操作順序不同不影響結(jié)果

   發(fā)現(xiàn)對(duì)于每一個(gè)黑點(diǎn)，一通操作過(guò)后它擴(kuò)展出的區(qū)域是一個(gè)矩形，而操作順序是不影響這個(gè)矩形的大小和位置的。

2. 最后的要求 “任意兩個(gè)黑色格子八連通” 等價(jià)于 “一開(kāi)始圖中的黑色格子八連通”。

   這是顯然的，因?yàn)閷?duì)于一個(gè)黑點(diǎn)，它擴(kuò)展出來(lái)的格子是個(gè)矩形，肯定八連通，所以我們只需要求一開(kāi)始圖中給定的黑點(diǎn)在最后八連通就好了。

   那么對(duì)于兩個(gè)黑點(diǎn)，操作它們同時(shí)往左擴(kuò)展一格，可以看作是讓這兩個(gè)黑點(diǎn)的水平距離減?\(1\)。

   不妨把八連通分為直接八連通和間接八連通兩種，那么這兩個(gè)黑點(diǎn)直接八連通就可以看成當(dāng)兩個(gè)黑點(diǎn)的水平和豎直距離都小于等于?\(1\)?時(shí)，間接八連通就是有一個(gè)黑點(diǎn)同時(shí)與它們八連通時(shí)。

3. 往左/右是等效的，往上/下同理

   對(duì)于兩個(gè)黑點(diǎn)，你操作它們同時(shí)往左擴(kuò)展或同時(shí)往右擴(kuò)展，出現(xiàn)的結(jié)果都是這兩個(gè)黑點(diǎn)的水平間距減?\(1\)，所以是等效的。

   我們不妨設(shè)?\(L\)?表示左/右操作的個(gè)數(shù)，\(U\)?表示上/下操作的個(gè)數(shù)，那么在這?\(L+U\)?次操作后，所有點(diǎn)的水平距離減小?\(L\)，豎直距離減小?\(U\)，現(xiàn)在要求使得所有黑點(diǎn)八連通的?\(L+U\)?的最小值。

考慮兩個(gè)黑點(diǎn)?\((x_1,y_1)\)?和?\((x_2,y_2)\)?什么時(shí)候直接八連通。顯然，當(dāng)?\(|x_1-x_2|\leq L+1\)?且?\(|y_1-y_2|\leq U+1\)?時(shí)，它們才直接八連通。

不妨將黑點(diǎn)間兩兩建邊，其中一條邊包含兩個(gè)關(guān)鍵字，第一關(guān)鍵字為?\(a=|x_1-x_2|\)，第二關(guān)鍵字為?\(b=|y_1-y_2|\)。不妨將這個(gè)圖命名為?\(A\)。

假設(shè)?\(L\)?已經(jīng)固定了，要求最小的?\(U\)。那么我們現(xiàn)在只能保留第一關(guān)鍵字?\(a\leq L+1\)?的邊，建成一個(gè)圖，不妨稱(chēng)其為?\(B\)。然后我們現(xiàn)在要找到一個(gè)最小的?\(U\)，使得在?\(B\)?圖的基礎(chǔ)上，只保留第二關(guān)鍵字?\(b\leq U+1\)?的邊也能使整個(gè)圖聯(lián)通。

也就是說(shuō)讓你在?\(B\)?圖中選出一些邊，使得只保留這些邊的圖仍然聯(lián)通而且這些邊的第二關(guān)鍵字?\(b\)?的最大值最小。

容易發(fā)現(xiàn)這就是求這個(gè)圖在邊以?\(b\)?為權(quán)值的情況下的最小生成樹(shù)的最大邊權(quán)，因?yàn)樽钚∩蓸?shù)不僅滿(mǎn)足邊之和最小，而且滿(mǎn)足最大邊也是最小的。（可以聯(lián)系 kruskal 的實(shí)現(xiàn)過(guò)程簡(jiǎn)單證明）

但是你發(fā)現(xiàn)如果這樣連，邊數(shù)可能達(dá)到?\((nm)^4\)，是無(wú)法接受的。

于是考慮如何如何簡(jiǎn)化連邊。

由于邊的權(quán)值定義只與點(diǎn)的坐標(biāo)有關(guān)，所以會(huì)發(fā)現(xiàn)下面這么一種情況：

明顯地，我們連不連?\((A,C)\)?這條邊都沒(méi)有關(guān)系，因?yàn)檫?\((A,B)\)?和邊?\((B,C)\)?的第一關(guān)鍵字（水平距離）和第二關(guān)鍵字（豎直距離）都比邊?\((A,C)\)?的小，而且連了邊?\((A,B)\)?和?\((B,C)\)?就已經(jīng)能使?\(A\)、\(C\)?八連通。

因此，一般地，對(duì)于任意兩個(gè)黑點(diǎn)?\(A\)、\(C\)，以?\(A\)、\(C\)?為對(duì)角作矩形（矩形的邊水平或豎直），如果這個(gè)矩形中（包含矩形的邊）包含另一個(gè)黑點(diǎn)?\(B\)，那么?\((A,C)\)?這條邊我們就可以不用連，因?yàn)檫B?\((A,B)\)?和?\((B,C)\)?就夠了。

那么簡(jiǎn)化過(guò)這個(gè)圖后，邊數(shù)最多能達(dá)到多少呢？

考慮構(gòu)造最大的邊數(shù)。

不妨設(shè)當(dāng)前圖中已經(jīng)有若干黑點(diǎn)了，這些黑點(diǎn)構(gòu)成的集合為?\(S\)，那么如果我再往這個(gè)集合里加入一個(gè)黑點(diǎn)?\(B\)，那么?\(B\)?肯定要和其它黑點(diǎn)連邊，或者說(shuō)滿(mǎn)足了上面的化簡(jiǎn)條件，把某條邊?\((A,C)\)?去掉，增加邊?\((A,B)\)?和?\((B,C)\)。但不論怎樣總邊數(shù)都是會(huì)增加的。

那么我們得到一個(gè)結(jié)論：總點(diǎn)數(shù)越多，總邊數(shù)越多。

那么當(dāng)整個(gè)網(wǎng)格圖都是黑點(diǎn)時(shí)，總邊數(shù)取到最大值，此時(shí)總邊數(shù)為?\((n-1)m+(m-1)n=2nm-n-m\)，是?\(nm\)?級(jí)別的。

發(fā)現(xiàn)這樣是可行的，但簡(jiǎn)化過(guò)程如何實(shí)現(xiàn)？

如果把圖建出來(lái)再簡(jiǎn)化，邊的級(jí)別是?\((nm)^2\)?級(jí)別的，不能接受。

所以考慮直接找簡(jiǎn)化后剩下的邊。

不妨把簡(jiǎn)化后的邊分成兩類(lèi)：斜右向下的和斜左向下的（可以把橫著的和豎著的歸到其中一類(lèi)去）。

以找斜右向下的邊為例：

對(duì)于一個(gè)點(diǎn)?\(A\)，我們找以它為起點(diǎn)的斜右向下的邊的終點(diǎn)有哪些。

發(fā)現(xiàn)其實(shí)就是要維護(hù)?\(A\)?右下角的一段以黑點(diǎn)構(gòu)成的最高的縱坐標(biāo)單增點(diǎn)集，類(lèi)似維護(hù)一個(gè)反比例函數(shù)?\(y=\dfrac{k}{x}(k<0)\)?的第四象限“”部分：

（其中紅點(diǎn)為?\(A\)，藍(lán)點(diǎn)是我們要維護(hù)的點(diǎn)）

那么終點(diǎn)就是這些藍(lán)色的點(diǎn)。

所以我們用一個(gè)單調(diào)棧來(lái)維護(hù)這些點(diǎn)就好了，具體實(shí)現(xiàn)過(guò)程詳見(jiàn)代碼。

那么斜左向下的邊也同理。

簡(jiǎn)化的時(shí)間復(fù)雜度是?\(O(nm)\)?的，可以接受。

接下來(lái)的問(wèn)題就是如何找到合適的?\(L\)?和?\(U\)?了。

首先蹦出來(lái)的想法是二分?\(L\)，但?\(L\)?越大，能考慮的邊就越多，\(U\)?就越小，而我們要求的是?\(L+U\)?的最小值，所以不能二分。

所以只能枚舉?\(L\)，那么我們就需要找出第一關(guān)鍵字?\(a\leq L\)?的邊，然后求它們以第二關(guān)鍵字?\(b\)?為權(quán)值的最小生成樹(shù)。

如果直接跑 kruskal 的時(shí)間是?\(O(nm\log (nm))\)，再乘上個(gè)枚舉?\(L\)?的時(shí)間就是?\(O(n^2m\log(nm))\)?了，不能接受。

假設(shè)你現(xiàn)在枚舉到?\(L\)，你發(fā)現(xiàn)從?\(L-1\)?到?\(L\)?過(guò)程中需要考慮的邊只是多了幾條而已，而?\(L\)?從?\(1\)?到?\(m\)?的過(guò)程中邊數(shù)最多只會(huì)增加?\(nm\)?條，所以考慮動(dòng)態(tài)維護(hù)最小生成樹(shù)。

于是自然而然地就聯(lián)想到 LCT 了。

用 LCT 動(dòng)態(tài)維護(hù)最小生成樹(shù)的具體過(guò)程是：假設(shè)當(dāng)前生成樹(shù)為?\(T\)，新加入的邊為?\((u,v)\)，邊權(quán)為?\(x\)。那么在當(dāng)前生成樹(shù)?\(T\)?的?\(u\)?到?\(v\)?的路徑上，找到邊權(quán)最大的邊，設(shè)其為?\((a,b)\)，邊權(quán)為?\(y\)。如果?\(x<y\)，我們就把邊?\((a,b)\)?刪掉，加入邊?\((u,v)\)。

但是還有兩個(gè)細(xì)節(jié)的地方：

1. LCT 如何維護(hù)邊權(quán)？

   最簡(jiǎn)單也最直接的方法就是把每一條邊拆成一個(gè)點(diǎn)，然后維護(hù)點(diǎn)權(quán)。

   還有一種神奇的方法，具體可以參考這篇博客。

   當(dāng)然無(wú)論哪種方法，時(shí)間復(fù)雜度都不會(huì)變大。

2. 如何維護(hù)全局邊權(quán)最大值？

   用 LCT 維護(hù)也不是不可以，具體做法可以參考上面的那篇講維護(hù)邊權(quán)的博客，它也有講如何維護(hù)子樹(shù)信息。

   但更暴力的做法是直接用一個(gè)?multiset維護(hù)全局的邊權(quán)，LCT 刪邊的時(shí)候在?multiset里面?\(\operatorname{erase}\)，加邊的時(shí)候直接在?multiset里面?\(\operatorname{insert}\)。

   總感覺(jué)讓 LCT 和 set 同時(shí)跑有點(diǎn)浪費(fèi)。

所有的細(xì)節(jié)也就處理完了，最后的時(shí)間復(fù)雜度是?\(O(nm \log (nm))\)。

感覺(jué)這道題涉及的面挺廣的，也很毒瘤。

具體代碼如下：

#include<bits/stdc++.h> #define N 1010 #define INF 0x7fffffff #define lc(u) (t[u].ch[0]) #define rc(u) (t[u].ch[1]) using namespace std; struct Point { int x,y; Point(){}; Point(int xx,int yy){x=xx,y=yy;} }sta[N]; struct Edge { int u,v,x,y;//x表示第二關(guān)鍵字，y表示第一關(guān)鍵字 Edge(){}; Edge(int uu,int vv,int xx,int yy){u=uu,v=vv,x=xx,y=yy;} }e[N*N*2]; struct data { int l,u,r; data(){}; data(int a,int b,int c){l=a,u=b,r=c;} }; struct Splay { int ch[2],fa,val,maxn; data p,maxp;//maxp存的是最大邊對(duì)應(yīng)點(diǎn)的編號(hào)，以及這條邊的兩個(gè)端點(diǎn)的編號(hào) bool rev; }t[N*N*3]; int st[N*N*3]; int n,m,node,top,tot,sumb; int added,ans=INF; int id[N][N],nxtl[N][N],nxtr[N][N]; bool vis[N][N]; multiset<int>s; bool cmp(Edge vis,Edge b) { return vis.y<b.y; } bool notroot(int u) { return lc(t[u].fa)==u||rc(t[u].fa)==u; } bool get(int u) { return rc(t[u].fa)==u; } void up(int u) { t[u].maxn=max(t[u].val,max(t[lc(u)].maxn,t[rc(u)].maxn)); if(t[u].maxn==t[u].val) t[u].maxp=t[u].p; else if(t[u].maxn==t[lc(u)].maxn) t[u].maxp=t[lc(u)].maxp; else t[u].maxp=t[rc(u)].maxp; } void downn(int u) { swap(lc(u),rc(u)); t[u].rev^=1; } void down(int u) { if(t[u].rev) { downn(lc(u)),downn(rc(u)); t[u].rev=0; } } void rotate(int u) { int fa=t[u].fa,gfa=t[fa].fa; bool d1=get(u),d2=get(fa); int sonu=t[u].ch[d1^1]; if(notroot(fa)) t[gfa].ch[d2]=u; t[u].fa=gfa; t[u].ch[d1^1]=fa; t[fa].fa=u; t[fa].ch[d1]=sonu; t[sonu].fa=fa; up(fa); } void splay(int u) { int now=u,top=0; st[++top]=now; while(notroot(now)) st[++top]=now=t[now].fa; while(top) down(st[top--]); while(notroot(u)) { int fa=t[u].fa; if(notroot(fa)) { if(get(u)==get(fa)) rotate(fa); else rotate(u); } rotate(u); } up(u); } void access(int u) { for(int y=0;u;y=u,u=t[u].fa) { splay(u); rc(u)=y; up(u); } } void makeroot(int u) { access(u); splay(u); downn(u); } int findroot(int u) { access(u); splay(u); while(lc(u)) { down(u); u=lc(u); } splay(u); return u; } void link(int x,int y) { makeroot(x); t[x].fa=y; } void cut(int x,int y) { makeroot(x); findroot(y); t[y].fa=rc(x)=0; up(x); } void work(Edge a) { ++node; t[node].maxn=t[node].val=a.x; t[node].maxp=t[node].p=data(a.u,node,a.v); makeroot(a.u); if(findroot(a.v)!=a.u)//判斷u和v不連通 { added++; s.insert(a.x); link(a.u,node),link(node,a.v); return; } if(t[a.u].maxn>a.x) { s.erase(s.find(t[a.u].maxn)); s.insert(a.x); int l=t[a.u].maxp.l,u=t[a.u].maxp.u,r=t[a.u].maxp.r; cut(l,u),cut(u,r); link(a.u,node),link(node,a.v); return; } } int main() { t[0].maxn=t[0].val=-INF; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { char s[N]; scanf("%s",s+1); for(int j=1;j<=m;j++) { vis[i][j]=(s[j]=='1'); if(vis[i][j]) { id[i][j]=++node; t[node].maxn=t[node].val=-INF; } } } sumb=node; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(vis[i][j-1]) nxtl[i][j]=j-1;//nxtl[i][j]表示點(diǎn)(i,j)同一行左邊最近的黑點(diǎn)在哪里 else nxtl[i][j]=nxtl[i][j-1]; } for(int j=m;j>=1;j--) { if(vis[i][j+1]) nxtr[i][j]=j+1;//nxtr的定義與nxtl同理 else nxtr[i][j]=nxtr[i][j+1]; } } ? ?//斜右向下的邊 for(int j=1;j<=m;j++) { top=0;//通過(guò)單調(diào)棧維護(hù) for(int i=n;i>=1;i--) { if(nxtr[i][j])//每次找到(i,j)右邊最近的黑點(diǎn)，并把它加入到單調(diào)棧內(nèi) { while(top&&sta[top].y>=nxtr[i][j]) top--; sta[++top]=Point(i,nxtr[i][j]); } if(vis[i][j]) { while(top) { e[++tot]=Edge(id[i][j],id[sta[top].x][sta[top].y],abs(sta[top].x-i),abs(sta[top].y-j));//當(dāng)前點(diǎn)同棧內(nèi)的所有點(diǎn)連邊，并把棧內(nèi)的點(diǎn)刪除 top--; } sta[++top]=Point(i,j);//重新加入當(dāng)前點(diǎn) } } } ? ?//斜左向下的邊同理 for(int j=m;j>=1;j--) { top=0; for(int i=n;i>=1;i--) { if(nxtl[i][j]) { while(top&&sta[top].y<=nxtl[i][j]) top--; sta[++top]=Point(i,nxtl[i][j]); } if(vis[i][j]) { while(top) { if(sta[top].x!=i&&sta[top].y!=j) e[++tot]=Edge(id[i][j],id[sta[top].x][sta[top].y],abs(sta[top].x-i),abs(sta[top].y-j));//這里加判斷是因?yàn)闄M著的和豎著的邊已經(jīng)在第一類(lèi)中討論過(guò)了，所以不必再加一遍 top--; } sta[++top]=Point(i,j); } } } if(!tot)//特判只有一個(gè)點(diǎn)（沒(méi)有邊） { puts("0"); return 0; } sort(e+1,e+tot+1,cmp); int tmp=1; for(int L=0;L<=m;L++)//枚舉L { while(tmp<=tot&&e[tmp].y<=L+1)//加入所有符合要求的邊 { work(e[tmp]); tmp++; } if(added==sumb-1)//如果能構(gòu)成樹(shù)（圖聯(lián)通） ans=min(ans,L+max(0,(*(--s.end()))-1)); } printf("%d\n",ans); return 0; } /* 2 5 10001 01010 */

常數(shù)挺大的（特別是拆點(diǎn)和加了?multiset以后）。

但還是因?yàn)楹苌偃私贿@道題跑到了洛谷最優(yōu)解。

鏈接：https://www.dianjilingqu.com/590885.html