正題

題面鏈接:https://gmoj.net/senior/#main/show/5057

---

題目大意

$n?m$的網格上有一些炮和敵軍，每個炮可以攻擊在它方向上一個敵軍，但是要求炮彈的軌跡不能交叉。求最多打死多少敵軍。

---

解題思路

我們先把炮分成兩類，一類是橫著打（定義為正類），一類是豎著打（定義為負類），那么肯定是兩類不同的軌跡交叉。
我們對于每個炮彈，它每走一格，可能能夠多打一些敵方，我們可以把這個多大的定義為這個點的權值。顯然對于每一類，格子都會有一個權值。

然后我們大致構建一個這樣的圖（炮1的第二個與炮2的第二個有交叉）

• 割掉權值為$w$（這里的$w$統指那個點在那一類的權值）的邊表示不選擇這個點
• 正類的邊連向炮的方向是因為如果我們要讓交叉的那條邊不生效，也就是要把后面三個的$w$權值舍棄，那么就表示炮彈不會打到后面那三個
• 反類的邊從炮彈出去也是一個原理，我們要求舍去的一定是一個后綴

然后這就是一個經典的最大權閉合圖模板了，上網絡流即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=6000,inf=2147483647/3; const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; struct node{int to,next,w; }a[N<<8]; int n,m,tot,s,t,cnt,ans; int dep[N],ls[N]; int v[51][51],wv[51][51]; queue<int> q; void addl(int x,int y,int w){if(!w)return;a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;return; } bool bfs(){memset(dep,0,sizeof(dep));dep[s]=1;while(!q.empty())q.pop();q.push(s);while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[y]||!a[i].w)continue;dep[y]=dep[x]+1;if(y==t)return 1;q.push(y);}}return 0; } int dinic(int x,int flow){int rest=0,k;if(x==t)return flow;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(dep[x]+1!=dep[y]||!a[i].w)continue;rest+=(k=dinic(y,min(flow-rest,a[i].w)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return flow;}if(!rest)dep[x]=0;return rest; } int main() {scanf("%d%d",&n,&m);s=0;t=cnt=tot=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&wv[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int tmp=0,x=i,y=j;if(wv[x][y]<0){int k=-wv[x][y]-1,last=++cnt,tmpp=0;if(k>1)continue;while(1){x+=dx[k];y+=dy[k];if(x<1||y<1||x>n||y>m)break;tmp=max(tmp,wv[x][y]);cnt++;addl(s,cnt,tmp-tmpp);if(last)addl(cnt,last,inf);tmpp=tmp;last=v[x][y]=cnt;}ans+=tmp;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int tmp=0,x=i,y=j;if(wv[x][y]<0){int k=-wv[x][y]-1,last=++cnt,tmpp=0;if(k<2)continue;while(1){x+=dx[k];y+=dy[k];if(x<1||y<1||x>n||y>m)break;tmp=max(tmp,wv[x][y]);cnt++;addl(cnt,t,tmp-tmpp);if(last)addl(last,cnt,inf);if(v[x][y])addl(v[x][y],cnt,inf);tmpp=tmp;last=cnt;}ans+=tmp;}}while(bfs())ans-=dinic(s,inf);printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的jzoj5057-[GDSOI2017模拟4.13]炮塔【网络流,最大权闭合图】的全部內容，希望文章能夠幫你解決所遇到的問題。

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