很明顯網(wǎng)絡(luò)流。

S到每個(gè)發(fā)射站連邊，容量為該站限制

每個(gè)接收站到T連邊，容量為該站限制

矩陣每個(gè)點(diǎn)拆成兩個(gè)點(diǎn)i和i',i向i'連邊，容量為該位置手機(jī)數(shù)

每個(gè)發(fā)射站向該正方形內(nèi)所有點(diǎn)i連邊，容量為無(wú)窮大

每個(gè)接收站向該正方形內(nèi)所有點(diǎn)i'連邊，容量為無(wú)窮大

求最大流即可。

?

但是這樣的話，TLE+MLE（內(nèi)存限制只有32M）

可以發(fā)現(xiàn)每個(gè)站點(diǎn)連出去的都是一個(gè)正方形，所以有種神奇的優(yōu)化方法

跟A+B Problem類(lèi)似，那道題是每次連的一定是個(gè)區(qū)間，所以建立線段樹(shù)后用一個(gè)點(diǎn)代表一個(gè)區(qū)間，父節(jié)點(diǎn)向兒子節(jié)點(diǎn)連邊

這題也類(lèi)似，不過(guò)因?yàn)檫B得容量都是無(wú)窮大，所以[1,10]這個(gè)區(qū)間即使被拆成[1,8][2,10]都不影響答案，

所以可以用二維ST表來(lái)優(yōu)化，

fs[i][j][k]表示左上角為(i,j)，邊長(zhǎng)為$2^k$的正方形所代表的點(diǎn)的ID

ft[i][j][k]表示左上角為(i,j)，邊長(zhǎng)為$2^k$的正方形所代表的點(diǎn)拆點(diǎn)后另一個(gè)點(diǎn)的ID

很明顯fs[i][j][0]要向ft[i][j][0]連邊，容量為(i,j)處手機(jī)數(shù)量

然后是預(yù)處理

?

fs[i][j][k]

向

fs[i][j][k-1]

fs[i+2^(k-1)-1][j][k-1]

fs[i][j+2^(k-1)-1][k-1]

fs[i+2^(k-1)-1][j+2^(k-1)-1][k-1]

連邊，容量為無(wú)窮大

?

ft[i][j][k-1]

ft[i+2^(k-1)-1][j][k-1]

ft[i][j+2^(k-1)-1][k-1]

ft[i+2^(k-1)-1][j+2^(k-1)-1][k-1]

向

ft[i][j][k]

連邊，容量為無(wú)窮大

?

對(duì)于每個(gè)發(fā)射站，

向

fs[x1][y1][log(邊長(zhǎng))]

fs[x1][y2-2^log(邊長(zhǎng))+1][log(邊長(zhǎng))]

fs[x2-2^log(邊長(zhǎng))+1][y1][log(邊長(zhǎng))]

fs[x2-2^log(邊長(zhǎng))+1][y2-2^log(邊長(zhǎng))+1][log(邊長(zhǎng))]

連邊，容量為無(wú)窮大

?

對(duì)于每個(gè)接收站，

ft[x1][y1][log(邊長(zhǎng))]

ft[x1][y2-2^log(邊長(zhǎng))+1][log(邊長(zhǎng))]

ft[x2-2^log(邊長(zhǎng))+1][y1][log(邊長(zhǎng))]

ft[x2-2^log(邊長(zhǎng))+1][y2-2^log(邊長(zhǎng))+1][log(邊長(zhǎng))]

向它連邊，容量為無(wú)窮大

?

這樣點(diǎn)數(shù)是$n^2\log n+a+b$，邊數(shù)是$n^2\log n+a+b$，就可以過(guò)了

?

#include<cstdio> inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} const int N=56010,inf=~0U>>2; int n,S,T,h[N],gap[N],maxflow; struct edge{int t,f;edge *nxt,*pair;}*g[N],*d[N]; int r,c,a,b,x1,x2,y1,y2,w; int i,j,k,fs[62][62][6],ft[62][62][6],pow[8],log[62]; inline int min(int a,int b){return a<b?a:b;} inline void add(int s,int t,int f){edge *p=new(edge);p->t=t;p->f=f;p->nxt=g[s];g[s]=p;p=new(edge);p->t=s;p->f=0;p->nxt=g[t];g[t]=p;g[s]->pair=g[t];g[t]->pair=g[s]; } int sap(int v,int flow){if(v==T)return flow;int rec=0;for(edge *p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f){int ret=sap(p->t,min(flow-rec,p->f));p->f-=ret;p->pair->f+=ret;d[v]=p;if((rec+=ret)==flow)return flow;}d[v]=g[v];if(!(--gap[h[v]]))h[S]=T;gap[++h[v]]++;return rec; } int main(){for(pow[0]=i=1;i<8;i++)pow[i]=pow[i-1]<<1;for(i=1;i<62;i++)for(j=i;j>1;j>>=1,log[i]++);read(r);read(c);read(a);read(b);for(i=1;i<=r;i++)for(j=1;j<=c;j++){fs[i][j][0]=++n,ft[i][j][0]=++n;read(k);add(fs[i][j][0],ft[i][j][0],k);}for(k=1;k<6;k++)for(i=1;i<=r;i++)for(j=1;j<=c;j++)if(i+pow[k]-1<=r&&j+pow[k]-1<=c){fs[i][j][k]=++n,ft[i][j][k]=++n;add(fs[i][j][k],fs[i][j][k-1],inf),add(ft[i][j][k-1],ft[i][j][k],inf);add(fs[i][j][k],fs[i+pow[k-1]][j][k-1],inf),add(ft[i+pow[k-1]][j][k-1],ft[i][j][k],inf);add(fs[i][j][k],fs[i][j+pow[k-1]][k-1],inf),add(ft[i][j+pow[k-1]][k-1],ft[i][j][k],inf);add(fs[i][j][k],fs[i+pow[k-1]][j+pow[k-1]][k-1],inf),add(ft[i+pow[k-1]][j+pow[k-1]][k-1],ft[i][j][k],inf);}S=n+a+b+1;T=S+1;while(a--){read(w),read(x1),read(y1),read(x2),read(y2);add(S,i=++n,w);k=log[j=x2-x1+1];add(i,fs[x1][y1][k],inf);add(i,fs[x1][y2-pow[k]+1][k],inf);add(i,fs[x2-pow[k]+1][y1][k],inf);add(i,fs[x2-pow[k]+1][y2-pow[k]+1][k],inf);}while(b--){read(w),read(x1),read(y1),read(x2),read(y2);add(i=++n,T,w);k=log[j=x2-x1+1];add(ft[x1][y1][k],i,inf);add(ft[x1][y2-pow[k]+1][k],i,inf);add(ft[x2-pow[k]+1][y1][k],i,inf);add(ft[x2-pow[k]+1][y2-pow[k]+1][k],i,inf);}gap[0]=T;for(i=0;i++<T;)d[i]=g[i];while(h[S]<T)maxflow+=sap(S,inf);printf("%d",maxflow);return 0; }

　　

?

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

總結(jié)

以上是生活随笔為你收集整理的BZOJ3577 : 玩手机的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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