Magic Slab

链接：https://ac.nowcoder.com/acm/contest/847/F
来源：牛客网

lililalala得到了一块魔法板，这块魔法板可以被看做大小为\ n \times n n×n的矩形，它含有\ n \times n n×n个单元格。
lililalala可以通过点亮这块魔法板的某些部分获得一定的能量值。
给定两个长度为\ n n的数列\ a a和\ b b以及一个\ n \times n n×n的矩阵\ c c。具体规则如下:
可以花费\ a_{i} a
i
​
点能量点亮魔法板（从上往下，下同）的第\ i i行\ (1 \le i \le n) (1≤i≤n)。
可以花费\ b_{i} b
i
​
点能量点亮魔法板（从左往右，下同）的第\ i i列\ (1 \le i \le n) (1≤i≤n)。
如果第\ i i行和第\ j j列同时被点亮，那么就认为第\ i i行的第\ j j个单元格被点亮，可以获得\ c_{ij} c
ij
​
点能量\ (1 \le i,j \le n) (1≤i,j≤n)。
此外魔法板有额外的关联奖励，每条关联奖励包含两个单元格，也就是说如果如果同时点亮了两个单元格且它们之间有关联奖励，那么就能额外获得一部分能量。
假设lililalala初始有足够多的能量，他想知道采取最优策略后他最多能赚取多少能量？(赚取的能量=获得的能量-消耗的能量)。
输入描述:
第一行两个整数\ n,m(1 \le n \le 40,0 \le m \le 1000) n,m(1≤n≤40,0≤m≤1000)–魔法板的大小和关联奖励的条数。
然后的\ n n行表示矩阵\ c c，\ n n行中的第\ i i行第\ j j个整数表示\ c_{ij} c
ij
​
(1 \le c_{ij} \le 5000)(1≤c
ij
​
≤5000)–点亮第\ i i行的第\ j j个单元格可以获得的能量。
然后的一行\ n n个整数\ a_{1},a_{2},a_{3}…a_{n} ( \ 1 \leq \ a_{1},a_{2},a_{3}…a_{n} \leq 5000 ) a
1

点能量。
输出描述:
输出一行包含一个整数–lililalala最多能赚取的能量。
示例1
输入
复制
2 0
3 1
1 5
2 2
2 2
输出
复制
2
示例2
输入
复制
3 1
12 3 7
4 8 1
1 2 8
2 9 7
3 15 4
3 1 3 3 8
输出
复制
20

明显的最大权闭合子图，对于收益和花费建图最小割即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+10,M=1e6+10;
int n,m,s,t,base,x,res,h[N];
int head[N],nex[M],to[M],w[M],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
inline int id(int x,int y){
	return (x-1)*n+y;
}
inline int bfs(){
	memset(h,0,sizeof h);	h[s]=1;	queue<int> q;	q.push(s);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
signed main(){
	cin>>n>>m;	base=n*n;	t=base+2*n+m+10;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>x;	add(s,id(i,j),x);	res+=x;
			add(id(i,j),base+j,inf);	add(id(i,j),base+n+i,inf);
		}
	}
	for(int i=1;i<=n;i++)	cin>>x,add(base+n+i,t,x);
	for(int i=1;i<=n;i++)	cin>>x,add(base+i,t,x);
	for(int i=1;i<=m;i++){
		int x1,y1,x2,y2,k;	cin>>x1>>y1>>x2>>y2>>k;	res+=k;	int d=i+base+2*n;
		add(s,d,k); add(d,base+n+x1,inf); add(d,base+n+x2,inf);
		add(d,base+y1,inf);	add(d,base+y2,inf);
	}
	cout<<res-dinic()<<endl;
	return 0;
}