本文共 1805 字，大约阅读时间需要 6 分钟。

很明显的最大权闭合子图模型

格子$(i,j)$的收益依赖于$i,j$是否被点亮

那么把行列拆分为$n+m$个点

每个格子向对应的行和列连边权为$inf$的边

$S$连向格子权值为收益,行列连向$T$权值为代价

至于奖励边,$S$连向奖励边的虚拟点,权值为奖励

虚拟点连向两个相关的格子,权值为$inf$

跑一边最小割即可。

#include 
   
    using namespace std;const int maxn = 3e5+10;const int inf = 1e9;struct edge{
   	int to,nxt,flow;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int flow){
   	d[++cnt] = (edge){
   v,head[u],flow},head[u] = cnt;	d[++cnt] = (edge){
   u,head[v],0},head[v] =cnt;}int dis[maxn],n,m,s,t,ans;bool bfs(){
   	for(int i=s;i<=t;i++)	dis[i] = 0;	queue
    
     q; q.push( s ); dis[s] = 1;	while( !q.empty() )	{
   		int u = q.front(); q.pop();		for(int i=head[u];i;i=d[i].nxt )		{
   			int v = d[i].to;			if( dis[v]==0&&d[i].flow )			{
   				dis[v] = dis[u]+1;				q.push( v );				if( v==t )	return true;			}		}	}	return false;}int dinic(int u,int flow){
   	if( u==t )	return flow;	int res = flow;	for(int i=head[u];i&&res;i=d[i].nxt )	{
   		int v = d[i].to;		if( dis[v]==dis[u]+1 && d[i].flow )		{
   			int temp = dinic( v,min(d[i].flow,res));			if( temp==0 )	dis[v] = 0;			d[i].flow-=temp,d[i^1].flow+=temp;			res-=temp;		}	}	return flow-res;}int id(int x,int y){
    return (x-1)*n+y; }int main(){
   	cin >> n >> m;	s=0, t = m+n*n+n+n+1;	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)		{
   			int x; cin >> x; ans += x;			add( id(i,j),i+n*n,inf);//行 			add( id(i,j),n*n+n+j,inf);//列 			add(s,id(i,j),x);		}	for(int i=1;i<=n;i++)		{
   	int x; cin >> x; add(n*n+i,t,x);  }//行 	for(int i=1;i<=n;i++)		{
   	int x; cin >> x; add(n*n+n+i,t,x); }//列 	for(int i=1;i<=m;i++)	{
   		int q,w,e,r,x; cin >> q >> w >> e >> r >> x;		add( n*(n+2)+i,id(q,w),inf );		add( n*(n+2)+i,id(e,r),inf );		add(s,n*(n+2)+i,x); ans += x;	}	while( bfs() )	ans -= dinic(s,inf );	cout << ans;}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112819517 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！