bzoj 4657 tower

Posted on | Views:

最小割.

  • 想到网络流应该不难,但关键是怎样建模.
  • 因为只有横向炮塔与竖向炮塔可能发生冲突,所以可以先套路地把一个点拆成一个横点和一个竖点,横点向对应竖点之间连一条边权为 $inf$ 的边.然后从源点 $S$ 向每个竖向攻击的炮塔的竖点连边权为 $inf$ 的边,从每个横向攻击的炮塔的横点向汇点 $T$ 连一条边权为 $inf$ 的边.
  • 考虑每个炮塔,选择一个点进行攻击,这个点显然是从炮塔出发到最大贡献所在点这条路径 $p$ 上的某个点.
  • 那么对于一个竖向攻击的炮塔,沿着路径 $p$ ,从炮塔到最大贡献点,相邻两点的竖点连上边.
  • 对于一个横向攻击的炮塔,沿着路径 $p$ ,从最大贡献点到炮塔,相邻两点的横点连上边.
  • 开始时钦定每个炮塔都打各自最大贡献点,收益为 $\sum max_i$ ,但这样会有路径相交,在图中表现为 $S$ 与 $T$ 连通.若一个炮塔改为打点 $u$ ,就把对应的路径 $p$ 上以 $u$ 为一端,另一端远离炮塔的点的边割掉就行了.减少的收益是 $max_i-val_u$ .可以发现,最后 $S$ 与 $T$ 不连通就与炮弹路径不相交是等价的.
  • 于是在路径 $p$ 上连边时,将边权设置为 $max_i-val_u$ ,用 $\sum max_i$ 减去最小割即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=1e9;
const int MAXN=2e5+10;
int ecnt=-1,head[MAXN],cur[MAXN],tot=0;
struct edge
{
	int nx,to,flow;
}E[MAXN];
void addedge(int u,int v,int w)
{
	++ecnt;
	E[ecnt].to=v;
	E[ecnt].nx=head[u];
	E[ecnt].flow=w;
	head[u]=ecnt;
}
void ins(int u,int v,int w)
{
	addedge(u,v,w);
	addedge(v,u,0);
}
int dep[MAXN];
bool bfs(int S,int T)
{
	queue<int> q;
	while(!q.empty())
		q.pop();
	for(int i=1;i<=tot;++i)
		cur[i]=head[i];
	memset(dep,-1,sizeof dep);
	dep[S]=0;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=E[i].nx)
		{
			int v=E[i].to;
			if(dep[v]==-1 && E[i].flow)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[T]!=-1;
}
int dfs(int u,int T,int limit)
{
	if(u==T || !limit)
		return limit;
	int f,flow=0;
	for(int i=cur[u];i!=-1;i=E[i].nx)
	{
		cur[u]=i;
		int v=E[i].to;
		if(dep[v]==dep[u]+1 && (f=dfs(v,T,min(limit,E[i].flow))))
		{
			limit-=f;
			flow+=f;
			E[i].flow-=f;
			E[i^1].flow+=f;
			if(!limit)
				break;
		}
	}
	return flow;
}
int Dinic(int S,int T)
{
	int maxflow=0;
	while(bfs(S,T))
		maxflow+=dfs(S,T,inf);
	return maxflow;
}
int n,m;
int node_id[51][51][2];//0:up/down 1:left/right
int org_graph[51][51];
int S,T,ans=0;
void build_graph(int x,int y,int tp)
{
	org_graph[x][y]=0;
	if(tp==1 || tp==2)
	{
		ins(S,node_id[x][y][0],inf);
		int mx=0,maxpos=-1;
		if(tp==1)
		{
			for(int i=x-1;i>=1;--i)
				if(org_graph[i][y]>mx)
					mx=org_graph[i][y],maxpos=i;
			if(maxpos==-1)
				return;
			for(int i=x-1;i>=maxpos;--i)
				ins(node_id[i+1][y][0],node_id[i][y][0],mx-org_graph[i+1][y]);
		}
		else
		{
			for(int i=x+1;i<=n;++i)
				if(org_graph[i][y]>mx)
					mx=org_graph[i][y],maxpos=i;
			if(maxpos==-1)
				return;
			for(int i=x+1;i<=maxpos;++i)
				ins(node_id[i-1][y][0],node_id[i][y][0],mx-org_graph[i-1][y]);
		}
		ans+=mx;
	}
	else
	{
		ins(node_id[x][y][1],T,inf);
		int mx=0,maxpos=-1;
		if(tp==3)
		{
			for(int j=y-1;j>=1;--j)
				if(org_graph[x][j]>mx)
					mx=org_graph[x][j],maxpos=j;
			if(maxpos==-1)
				return;
			for(int j=y-1;j>=maxpos;--j)
				ins(node_id[x][j][1],node_id[x][j+1][1],mx-org_graph[x][j+1]);
		}
		else
		{
			for(int j=y+1;j<=m;++j)
				if(org_graph[x][j]>mx)
					mx=org_graph[x][j],maxpos=j;
			if(maxpos==-1)
				return;
			for(int j=y+1;j<=maxpos;++j)
				ins(node_id[x][j][1],node_id[x][j-1][1],mx-org_graph[x][j-1]);
		}
		ans+=mx;
	}
}
int main()
{
	memset(head,-1,sizeof head);
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			org_graph[i][j]=read();
			node_id[i][j][0]=++tot;
			node_id[i][j][1]=++tot;
			ins(tot-1,tot,inf);
		}
	S=++tot,T=++tot;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(org_graph[i][j]<0)
				build_graph(i,j,-org_graph[i][j]);
	ans-=Dinic(S,T);
	cout<<ans<<endl;
	return 0;
}