Description

Nick最近在玩一款很好玩的游戲，游戲規則是這樣的：

有一個n*m的地圖，地圖上的每一個位置要么是空地，要么是炮塔，要么是一些BETA狗，Nick需要操縱炮塔攻擊BETA狗們。

攻擊方法是：對于每個炮塔，游戲系統已經給出它可以瞄準的方向(上下左右其中一個），Nick需要選擇它的攻擊位置，每一個炮塔只能夠攻擊一個位置，炮塔只能夠向著它的瞄準方向上的某個位置發動攻擊，當然炮塔也可以不進行攻擊。炮塔威力強大，它可以且僅可以消滅目標位置上所有的BETA狗。

出于安全考慮，游戲系統已經保證不存在一個炮塔能夠瞄準另外一個炮塔，即對于任意一個炮塔，它所有可能的攻擊位置上不存在另外一個炮塔。而且，如果把炮塔的起點和終點稱為炮彈的運行軌跡，那么系統不允許兩條軌跡相交f包括起點和終點）。

現在，選定目標位置以后，每一個炮塔同時開炮，你要告訴Nick，他最多可以干掉多少BETA狗。

Input

第一行兩個正整數n，m，表示地圖的規模。

接下來禮行，每行m個整數，0表示空地，-1，-2，一3，-4分別表示瞄準上下左右的炮塔，若為正整數p，則表示該位置有p個BETA狗。

n，m <= 50，每個位置的BETA狗數量不超過999個，保證不存在任意一個炮塔能夠瞄準另外一個炮塔

Output

一個正整數，表示Nick最多可以干掉幾個BETA狗

Sample Input

3 2

0 9

-4 3

0 -1

Sample Output

9

Solution

一道網絡流建模題，有關最小割

首先我們把每個點拆成兩個點，網上都稱為“橫點”和“豎點”，那我們也這樣叫

然后橫點只管橫向的邊，豎點只管豎向的邊，對于每一個點，它的豎點向橫點連一條邊權為 \(inf\) 的邊

左右攻擊的塔和上下攻擊的塔分開考慮

對于上下攻擊的塔，我們先建立一個超級源點，向所有上下攻擊的炮塔的豎點連一條邊權為 \(inf\) 的邊，然后找到這個塔能打到的最大的貢獻，然后從炮塔的豎點開始，每個點只向上面或下面相鄰的一個點連邊，一直連到最大的貢獻所在的位置，方向與炮塔攻擊方向相同，邊權暫時不管

這樣一個炮臺連出的邊就是它選擇一個攻擊目標后，所覆蓋的范圍

對于左右攻擊的塔，其實同理。建立一個超級匯點，向所有左右攻擊的塔的橫點連一條邊權為 \(inf\) 的邊，但方向是從塔到匯點。每個塔也是一直連到它的最大的貢獻所在的位置，但方向都是與塔的攻擊方向相反的，邊權不管

這樣建完一個圖后，我們默認每個塔都打的是它所能打到的最大的貢獻

但這樣顯然會相交

而相交的現象放到我們建的圖里表達出來就是超級源點與超級匯點是連通的

那么我們要做的就是在使他們不聯通的情況下，減去的貢獻最小

這就是最小割是怎么來的

然后我們要搞定這最小割是多少，就是我們建邊的邊權是什么

我們最開始不是默認每個炮臺選的是貢獻最大的點，那么一開始算的答案就是 \(\sum Max(i)\)

然后我們考慮一個炮臺，我們如果割掉其中一條邊，這條邊的出發點是 \(u\) ，而我們把這條邊割掉了，就相當于這個炮臺選 \(u\) 點攻擊，這時候這個炮臺的貢獻就變成了 \(val(u)\)，從 \(Max(i)\) 變成 \(val(u)\) 減少了 \(Max(i)-val(u)\) ，那么我們就把這條邊的邊權賦為這個東西，這樣割掉這條邊，最后減去答案的時候，就會使這個炮臺初始的貢獻變成真正的貢獻

也就是說

對于每一個上下攻擊的炮塔的攻擊范圍的豎點，我們建的邊的邊權都是所屬炮塔最大的貢獻減去這條邊的起點 \(u\) 的點權，這樣割掉了這條邊，就像當于選了 \(u\) 點

對于每一個左右攻擊的炮塔的攻擊范圍的橫點，我們建的邊的邊權都是所屬炮塔最大的貢獻減去這條邊的終點 \(v\) 的點權，這樣割掉了這條邊，就相當與選了 \(v\) 點

然后對于這個圖跑了最小割后，用最開始的答案減去最小化的割，就是最大化的貢獻了

#include<bits/stdc++.h> #define ll long long #define db double #define ld long double const int MAXN=50+10,MAXM=50000+10,inf=0x3f3f3f3f; int n,m,G[MAXN][MAXN],to[MAXM<<2],nex[MAXM<<2],cap[MAXM<<2],e=1,beg[MAXM],level[MAXM],ans,s,t,tot,cur[MAXM]; std::queue<int> q; template<typename T> inline void read(T &x) {T data=0,w=1;char ch=0;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();x=data*w; } template<typename T> inline void write(T x,char c='\0') {if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');if(c!='\0')putchar(c); } template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);} template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);} template<typename T> inline T min(T x,T y){return x<y?x:y;} template<typename T> inline T max(T x,T y){return x>y?x:y;} inline int id(int x,int y,int z) {return (x-1)*m+y+(z?n*m:0); } inline void insert(int x,int y,int z) {to[++e]=y;nex[e]=beg[x];beg[x]=e;cap[e]=z;to[++e]=x;nex[e]=beg[y];beg[y]=e;cap[e]=0; } inline void build(int x,int y,int dir) {int mp=0,pos=-1;G[x][y]=0;if(dir==-1){insert(s,id(x,y,0),inf);for(register int i=x-1;i>=1;--i)if(G[i][y]>mp)mp=G[i][y],pos=i;if(pos==-1)return ;for(register int i=x-1;i>=pos;--i)insert(id(i+1,y,0),id(i,y,0),mp-G[i+1][y]);}if(dir==-2){insert(s,id(x,y,0),inf);for(register int i=x+1;i<=n;++i)if(G[i][y]>mp)mp=G[i][y],pos=i;if(pos==-1)return ;for(register int i=x+1;i<=pos;++i)insert(id(i-1,y,0),id(i,y,0),mp-G[i-1][y]);}if(dir==-3){insert(id(x,y,1),t,inf);for(register int i=y-1;i>=1;--i)if(G[x][i]>mp)mp=G[x][i],pos=i;if(pos==-1)return ;for(register int i=y-1;i>=pos;--i)insert(id(x,i,1),id(x,i+1,1),mp-G[x][i+1]);}if(dir==-4){insert(id(x,y,1),t,inf);for(register int i=y+1;i<=m;++i)if(G[x][i]>mp)mp=G[x][i],pos=i;if(pos==-1)return ;for(register int i=y+1;i<=pos;++i)insert(id(x,i,1),id(x,i-1,1),mp-G[x][i-1]);}ans+=mp; } inline void init() {for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)insert(id(i,j,0),id(i,j,1),inf);s=n*m*2+1,t=n*m*2+2;for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)if(G[i][j]<0)build(i,j,G[i][j]),tot++; } inline bool bfs() {memset(level,0,sizeof(level));level[s]=1;q.push(s);while(!q.empty()){int x=q.front();q.pop();for(register int i=beg[x];i;i=nex[i])if(cap[i]&&!level[to[i]])level[to[i]]=level[x]+1,q.push(to[i]);}return level[t]; } inline int dfs(int x,int maxflow) {if(x==t||!maxflow)return maxflow;int res=0,f;for(register int &i=cur[x];i;i=nex[i])if(cap[i]&&level[to[i]]==level[x]+1){f=dfs(to[i],min(maxflow,cap[i]));cap[i]-=f;cap[i^1]+=f;maxflow-=f;res+=f;if(!maxflow)break;}return res; } inline int Dinic() {int res=0;while(bfs())memcpy(cur,beg,sizeof(cur)),res+=dfs(s,inf);return res; } int main() {read(n);read(m);for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)read(G[i][j]);init();if(!tot)write(0,'\n');else write(ans-Dinic(),'\n');return 0; }

轉載于:https://www.cnblogs.com/hongyj/p/8646446.html

總結

以上是生活随笔為你收集整理的【刷题】BZOJ 4657 tower的全部內容，希望文章能夠幫你解決所遇到的問題。

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