必备知识

网络流及dinic算法

最大流最小割定理

题目分析

回归正题。

这个题很明显是一个最小割好题。但做的人怎么这么少？

我们把每一个人视作一个点 $i$，规定：$i$被割到$S$集里，代表这个人选文，$i$被割到$T$集里，代表这个人选理.

将$S$连向这个点，长度为art，如果该边被割，则说明不选文，不能获得art的收益，可得到science的收益。

将这个点连向$T$，长度为science，如果该边被割，则说明不选理，不能获得science的收益，可得到art的收益。

那么对于同时选择的情况，我们可以新建点。

对于几个相邻的点，我们新建一个点，将$S$连向这个点，长度为同时选文可获得的收益，如果该边被割，则说明这些人不同时选文，不能获得同时选文可获得的收益。

同样，我们新建一个点，将这个点连向$T$，长度为同时选理可获得的收益，如果该边被割，则说明这些人不同时选理，不能获得同时选理可获得的收益，

怎么保证不割这条边则必然都选同样的科目呢？

我们可以将新建的点，向相邻的那几个点中的每一个点（或从相邻的那几个点中的每一个点向新建的点）连一条长度为$inf$的边，这样的边在最小割中肯定不会存在，则保证了在代表共同选择收益的边不被割时（即都选一个科目）新建的点与相邻的点在同一个点集。问题得以解决。

通过Dinic算法求得该图的最小割，总收益减最小割即为最大收益。

论证完毕。

建图方式

把每一个人视作一个点 $i$。

将$S$连向这个点，长度为art。

将这个点连向$T$，长度为science。

新建点，将$S$连向这个点，长度为同时选文可获得的收益，并向相邻的那几个点中的每一个点连一条长度为$inf$的边。

新建点，将这个点连向$T$，长度为同时选理可获得的收益，从相邻的那几个点中的每一个点向新建的点连一条长度为$inf$的边。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define Maxn 40001<<1
#define inf (unsigned)-1>>1
using namespace std;

int N,M;int S,T,sum,opt;
const int dx[6]={0,0,0,-1,1};
const int dy[6]={0,-1,1,0,0};
struct Edge {
	int v,flow,rev;
};
inline int read () {
    int X=0,w=1;char ch=0;
    while (ch<'0'||ch>'9')		{ if(ch=='-')	w=-1;ch=getchar(); }
    while (ch>='0'&&ch<='9')	{ X=(X<<1)+(X<<3)+ch-'0';ch=getchar(); }
    return X*w;
}
struct Graph {
	vector <Edge> e[Maxn];queue <int> Q;
	int level[Maxn];
	inline void addedge (int x,int y,int z) {
		e[x].push_back( (Edge){	y,z,e[y].size() } );
		e[y].push_back( (Edge){	x,0,e[x].size()-1} );
	}
	inline bool bfs () {
		memset(level,0,sizeof(level));
		Q.push(S);level[S]=1;
		while(!Q.empty()) {
			int u=Q.front();Q.pop();
			for(int i=0;i<e[u].size();i++) {
				int v=e[u][i].v;
				if( !level[v] && e[u][i].flow ) {
					level[v]=level[u]+1;
					Q.push(v);
				}
			}
		}
		return level[T];
	}
	int dfs (int x,int maxf) {
		if( x==T || maxf==0 )   return maxf;
		int pos=0;
		for(int i=0;i<e[x].size();i++) {
			int v=e[x][i].v;
			if( e[x][i].flow && level[v]==level[x]+1) {
				int f=dfs(v,min(e[x][i].flow,maxf));
				e[x][i].flow-=f;
				e[v][e[x][i].rev].flow+=f;
				pos+=f;
				maxf-=f;
			}
		}
		return pos;
	}
	inline int dinic () {
		int ans=0;
		while(bfs())    ans+=dfs(S,inf);
		return ans;
	}
} G ;
inline int getID (int i,int j) {
	return (i-1)*M+j;
}
int main () {
	N=read();M=read();S=0;T=N*M+1;opt=N*M+1;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int art=read(),id=getID(i,j);
			sum+=art;
			G.addedge(S,id,art);
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int science=read(),id=getID(i,j);
			sum+=science;
			G.addedge(id,T,science);
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int same_art=read(),id=getID(i,j);opt++;
			sum+=same_art;
			G.addedge(S,opt,same_art);
			G.addedge(opt,id,inf);
			for(int k=1;k<=4;k++)
				if( i+dx[k]>=1 && i+dx[k]<=N && j+dy[k]>=1 && j+dy[k]<=M )
					G.addedge(opt,getID(i+dx[k],j+dy[k]),inf);
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int same_science=read(),id=getID(i,j);opt++;
			sum+=same_science;
			G.addedge(opt,T,same_science);
			G.addedge(id,opt,inf);
			for(int k=1;k<=4;k++)
				if( i+dx[k]>=1 && i+dx[k]<=N && j+dy[k]>=1 && j+dy[k]<=M )
					G.addedge(getID(i+dx[k],j+dy[k]),opt,inf);
		}
	printf("%d\n",sum-G.dinic());
	return 0;
}

P4313 【文理分科】

$\color{green}{\text{更好的阅读体验}}$

题意

每个人选文科或理科可以有满意值，几个人同时选文科或理科也可以获得满意值，求满意值的最大值。

??为什么文科是art

题解

看到这类二者选其一的模型，我们肯定能想到最小割。首先，我们先从矩阵中拿出小盆友$A$和TA的相邻同学$B$、$C$、$D$、$E$，怼到图上，在画上源点和汇点，分别代表文科和理科：

假设没有额外的快乐值，我们可以这么连边：

如果我们割去一条边，就代表着不选文科/理科，若图不连通，则代表每个点只与源点或汇点联通，即每个人只选文科或理科。然后我们再去考虑$same$值，显然，我们如果选了一条$science$的边，就要把$same\ art$删掉；同理，我们如果选了一条$art$的边，就要把$same\ science$删掉，因此，我们可以加上两个虚点，连上边：

建完了图剩下的代码就简单了

代码

#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;
namespace in{
	char buf[1<<21],*p1=buf,*p2=buf;
	inline int getc(){
	    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
	}
	template <typename T>inline void read(T& t){
	    t=0;int f=0;char ch=getc();
	    while (!isdigit(ch)){
	        if(ch=='-')f = 1;
	        ch=getc();
	    }
	    while(isdigit(ch)){
   	    	t=t*10+ch-48;
   	    	ch = getc();
   		}
		if(f)t=-t;
	}
	template <typename T,typename... Args> inline void read(T& t, Args&... args){
	    read(t);read(args...);
	}
}
namespace out{
	char buffer[1<<21];
	int p1=-1;
	const int p2 = (1<<21)-1;
	inline void flush() {
		fwrite(buffer,1,p1+1,stdout),
		p1=-1;
	}
	inline void putc(const char &x) {
		if(p1==p2)flush();
		buffer[++p1]=x;
	}
	template <typename T>void write(T x) {
		static char buf[15];
		static int len=-1;
		if(x>=0){
			do{
    			buf[++len]=x%10+48,x/=10;
    		}while (x);
		}else{
    		putc('-');
			do {
    			buf[++len]=-(x%10)+48,x/=10;
			}while(x);
		}
		while (len>=0)
			putc(buf[len]),--len;
	}
}
const int maxn=4000010,maxe=100010*2;
struct Graph{
	struct node{
		int v,w,nxt;
	}e[maxe<<1];
	int head[maxn],cur[maxn],tot;
	int dis[maxn];
	int s,t;
	void init(int _s,int _t){s=_s,t=_t;tot=1;memset(head,0,sizeof head);}
	Graph(int _s=0,int _t=0){init(_s,_t);}
	void add(int u,int v,int w){
		//printf("%d %d %d\n",u,v,w);
		e[++tot]=(node){v,w,head[u]},head[u]=tot;
		e[++tot]=(node){u,0,head[v]},head[v]=tot;
	}
	#define v e[i].v
	inline bool bfs(){
		queue<int>q;
		memset(dis,0,sizeof dis);
		memcpy(cur,head,sizeof head);
		dis[s]=1;q.push(s);
		while(q.size()){
			int u=q.front();q.pop();
			for(int i=head[u];i;i=e[i].nxt)
				if(!dis[v]&&e[i].w){
					dis[v]=dis[u]+1,q.push(v);
					if(v==t)return true;
				}
		}
		return  false;
	}
	int dfs(int u,int flow){
		if(u==t)return flow;
		int rest=flow;
		for(int i=cur[u];i&&rest;i=e[i].nxt){
			if(dis[v]==dis[u]+1&&e[i].w){
				int tmp=dfs(v,min(rest,e[i].w));
				rest-=tmp,e[i].w-=tmp,e[i^1].w+=tmp;
			}
			cur[u]=i;
		}
		if(rest==0)dis[u]=-1;
		return flow-rest;
	}
	#undef v
	int dinic(){
		int ans=0;
		while(bfs())
			while(int sth=dfs(s,2e9))
				ans+=sth;
		return ans;
	}
}G;
int n,m,x;
int sum,tot;
bool check(int x,int y){
	return x<=n&&x>=1&&y<=m&&y>=1;
}
#define P(i,j) ((i)-1)*m+(j)
signed main(){
	//freopen("1.in","r",stdin);
	in::read(n,m);
	tot=n*m;G.init(0,++tot);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			in::read(x);sum+=x;
			G.add(G.s,P(i,j),x);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			in::read(x);sum+=x;
			G.add(P(i,j),G.t,x);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			in::read(x);sum+=x;
			G.add(G.s,++tot,x);
			G.add(tot,P(i,j),1e9);
			if(check(i,j-1))G.add(tot,P(i,j-1),1e9);
			if(check(i,j+1))G.add(tot,P(i,j+1),1e9);
			if(check(i-1,j))G.add(tot,P(i-1,j),1e9);
			if(check(i+1,j))G.add(tot,P(i+1,j),1e9);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			in::read(x);sum+=x;
			G.add(++tot,G.t,x);
			G.add(P(i,j),tot,1e9);
			if(check(i,j-1))G.add(P(i,j-1),tot,1e9);
			if(check(i,j+1))G.add(P(i,j+1),tot,1e9);
			if(check(i-1,j))G.add(P(i-1,j),tot,1e9);
			if(check(i+1,j))G.add(P(i+1,j),tot,1e9);
		}
	out::write(sum-G.dinic());
	out::flush();
}

举一反三

happiness

小M的作物

展示时间，220多ms

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
const ll inf=0x3f3f3f3f;
ll ar[110][110],sc[110][110],sa[110][110],ss[110][110];
ll num[110][110];
ll no=0,ans=0,s,t,n,m;
struct node{ll x,y,p,f;}a[30010<<5];
ll last[30010],alen=1;
ll h[30010],gap[30010];
ll maxflow=0,ex;
void ins(ll x,ll y,ll f)
{
	alen++;a[alen]={x,y,last[x],f};last[x]=alen;
	alen++;a[alen]={y,x,last[y],0};last[y]=alen;
}
void build()
{
	memset(last,-1,sizeof last);
	s=0,t=no*3+1;
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)
	{
		ll val=sc[i][j]-ar[i][j];
		if(val>=0)ins(s,num[i][j],val),ex+=val;
		else ins(num[i][j],t,-val);
	}
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)
	{
		ins(num[i][j],num[i][j]+no,inf);
		ins(num[i][j]+no,t,sa[i][j]);
		for(ll dir=0;dir<4;dir++)
		{
			ll nx=i+dx[dir],ny=j+dy[dir];
			if(nx<1||nx>n||ny<1||ny>m)continue;
			ins(num[i][j],num[nx][ny]+no,inf);
		}
	}
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)
	{
		ins(num[i][j]+(no<<1),num[i][j],inf);
		ins(s,num[i][j]+(no<<1),ss[i][j]);
		ex+=ss[i][j];
		for(ll dir=0;dir<4;dir++)
		{
			ll nx=i+dx[dir],ny=j+dy[dir];
			if(nx<1||nx>n||ny<1||ny>m)continue;
			ins(num[i][j]+(no<<1),num[nx][ny],inf);
		}
	}
}
void bfs()
{
	memset(h,0,sizeof h);h[t]=1;
	memset(gap,0,sizeof(gap));
	queue<ll>q;q.push(t);
	while(q.size())
	{
		ll x=q.front();q.pop();
		++gap[h[x]];
		for(ll k=last[x];k;k=a[k].p)if(a[k].f)
		{
			ll y=a[k].y;
			if(!h[y])h[y]=h[x]+1,q.push(y);
		}
	}
}
ll dfs(ll x,ll f)
{
	if(x==t)return f;
	ll sx=0;
	for(ll k=last[x];k;k=a[k].p)if(a[k].f)
	{
		ll y=a[k].y;
		if(h[y]+1==h[x])
		{
			ll sy=dfs(y,min(a[k].f,f-sx));
			a[k].f-=sy;a[k^1].f+=sy;
			sx+=sy;if(sx==f)return sx;
		}
	}
	if(!--gap[h[x]])h[s]=t+1;
	++gap[++h[x]];
	return sx;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)scanf("%lld",&ar[i][j]);
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)scanf("%lld",&sc[i][j]);
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)scanf("%lld",&sa[i][j]);
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)scanf("%lld",&ss[i][j]);
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)num[i][j]=++no;
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)ans+=ar[i][j];
	for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)ans+=sa[i][j];
	build();bfs();
	while(h[s]<=t)maxflow+=dfs(s,inf);
	printf("%lld\n",ans+ex-maxflow);
	return 0;
}

好不容易改好的码风，凑乎看吧

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=100010,M=1000010,inf=2e9;
struct node{int x,y;LL f;int pre;}a[M];int alen,last[M];
void ins(int x,int y,LL f)
{
	alen++;a[alen]={x,y,f,last[x]};last[x]=alen;
	alen++;a[alen]={y,x,0,last[y]};last[y]=alen;
}
int h[N],st,ed,n,m;
bool pd()
{
	deque<int>Q;Q.clear();
	memset(h,0,sizeof(h));h[st]=1;
	Q.push_back(st);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		for(int k=last[x];k;k=a[k].pre)if(a[k].f)
		{
			int y=a[k].y;
			if(h[y]==0)
			{
				h[y]=h[x]+1;
				Q.push_back(y);
			}
		}
	}
	return h[ed]>0;
}
LL dinic(int x,LL f)
{
	if(x==ed)return f;
	LL sx=0;
	for(int k=last[x];k;k=a[k].pre)if(a[k].f)
	{
		int y=a[k].y;
		if(h[y]==h[x]+1)
		{
			LL sy=dinic(y,min(f-sx,a[k].f));
			sx+=sy;a[k].f-=sy;a[k^1].f+=sy;
			if(f==sx)return sx;
		}
	}
	if(sx==0)h[x]=0;
	return sx;
}
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int get(int i,int j){return (i-1)*m+j;}
int main()
{
	scanf("%d%d",&n,&m);alen=1;
	st=0,ed=n*m+1;int opt=n*m+1;LL sum=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	{
		int art,id=get(i,j);
		scanf("%d",&art);
		sum+=art;
		ins(st,id,art);
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	{
		int sci,id=get(i,j);
		scanf("%d",&sci);
		sum+=sci;
		ins(id,ed,sci);
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	{
		int art,id=get(i,j);opt++;
		scanf("%d",&art);
		sum+=art;
		ins(st,opt,art);
		ins(opt,id,inf);
		for(int k=0;k<4;k++)
		{
			int xx=i+dx[k],yy=j+dy[k];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
				ins(opt,get(xx,yy),inf);
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	{
		int sci,id=get(i,j);opt++;
		scanf("%d",&sci);
		sum+=sci;
		ins(opt,ed,sci);
		ins(id,opt,inf);
		for(int k=0;k<4;k++)
		{
			int xx=i+dx[k],yy=j+dy[k];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
				ins(get(xx,yy),opt,inf);
		}
	}
	LL ans=0;
	while(pd())ans+=dinic(st,inf);
	printf("%lld\n",sum-ans);
	return 0;
}

#include<bits/stdc++.h>
#define check(x,y) (x>=1&&x<=n&&y>=1&&y<=m)
#define P(i,j) ((i-1)*m + (j))
using namespace std;
typedef long long ll;
const int N=4e6+10,inf=1e9;
struct Edge{int to,r;ll c;};
vector<Edge>G[N];
int d[N],st,ed,n,m,tot;
ll sum;
inline bool bfs(){
	memset(d,-1,sizeof d);
	queue<int>q;q.push(st);d[st]=0;
	while(q.size()){
		int u=q.front();q.pop();
		for(const Edge&e:G[u])
			if(e.c&&d[e.to]==-1){
				d[e.to]=d[u]+1;q.push(e.to);
				if(e.to==ed)return true;
			}
	}
	return false;
}
inline ll dfs(int u,ll mf){
	if(u==ed)return mf;
	ll t=0;
	for(Edge&e:G[u])
		if(e.c&&d[e.to]==d[u]+1){
			ll f=dfs(e.to,min(mf-t,e.c));
			e.c-=f;G[e.to][e.r].c+=f;t+=f;
			if(t==mf)break;
		}
	if(!t)d[u]=-1;
	return t;
}
inline ll dinic(){
	ll mf=0;
	while(bfs())mf+=dfs(st,1e18);
	return mf;
}
void add(int u,int v,ll c){
	G[u].push_back({v,(int)G[v].size(),c});
	G[v].push_back({u,(int)G[u].size()-1,0});
}
int main(){
	scanf("%d%d",&n,&m);
	tot=n*m;st=0;ed=++tot;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			ll x;scanf("%lld",&x);sum+=x;
			add(st,P(i,j),x);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			ll x;scanf("%lld",&x);sum+=x;
			add(P(i,j),ed,x);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			ll x;scanf("%lld",&x);sum+=x;
			int now=++tot;add(st,now,x);
			add(now,P(i,j),inf);
			if(check(i,j-1))add(now,P(i,j-1),inf);
			if(check(i,j+1))add(now,P(i,j+1),inf);
			if(check(i-1,j))add(now,P(i-1,j),inf);
			if(check(i+1,j))add(now,P(i+1,j),inf);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			ll x;scanf("%lld",&x);sum+=x;
			int now=++tot;add(now,ed,x);
			add(P(i,j),now,inf);
			if(check(i,j-1))add(P(i,j-1),now,inf);
			if(check(i,j+1))add(P(i,j+1),now,inf);
			if(check(i-1,j))add(P(i-1,j),now,inf);
			if(check(i+1,j))add(P(i+1,j),now,inf);
		}
	printf("%lld\n",sum-dinic());
	return 0;
}