【题解】[国家集训队]happiness

\(\text{Solution:}\)

显然还是一个分组问题。对于理科和文科我们可以看出最小割模型，而处理同时选择某一学科的时候，需要我们根据套路建立虚点处理。

同小M的作物一题，这题只不过是组数多了一点。

笔者前几次\(\color{red}{\text{WA}}\)是因为汇点编号小了，值得反思与铭记……

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN=5e5+10;

int tot=1,head[5000010],Ans;

int cur[MAXN],dep[MAXN];

int n,m,S,T,id;

const int inf=(1LL<<60);

struct E{int nxt,to,flow;}e[5000100];

inline void add(int x,int y,int w){

	e[++tot].to=y;e[tot].nxt=head[x];e[tot].flow=w;head[x]=tot;

	e[++tot].to=x;e[tot].nxt=head[y];e[tot].flow=0;head[y]=tot;

}

bool bfs(int s,int t){

	memset(dep,0,sizeof dep);

	queue<int>q;q.push(s);

	cur[s]=head[s];dep[s]=1;

	for(;!q.empty();){

		s=q.front();q.pop();

		for(int i=head[s];i;i=e[i].nxt){

			int j=e[i].to;

			if(!dep[j]&&e[i].flow){

				cur[j]=head[j];

				dep[j]=dep[s]+1;

				if(j==t)return true;

				q.push(j);

			}

		}

	}

	return false;

}

int dfs(int s,int flow,int t){

	if(flow<=0||s==t)return flow;

	int rest=flow;

	for(int i=cur[s];i;i=e[i].nxt){

		int j=e[i].to;

		if(dep[j]==dep[s]+1&&e[i].flow){

			int tmp=dfs(j,min(rest,e[i].flow),t);

			if(tmp<=0)dep[j]=0;

			rest-=tmp;e[i].flow-=tmp;e[i^1].flow+=tmp;

			if(rest<=0)break;

		}

	}

	return flow-rest;

}

int dinic(int s,int t){

	int ans=0;

	for(;bfs(s,t);)ans+=dfs(s,inf,t);

	return ans;

}

inline int pos(int i,int j){return (i-1)*m+j;}

inline int build(){return (++id);}

signed main(){

	scanf("%lld%lld",&n,&m);

	S=0,T=n*m+2*n*(m-1)+2*(n-1)*m+1;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j){

			int x;

			scanf("%lld",&x);

			Ans+=x;

			add(S,pos(i,j),x);

		}

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j){

			int x;

			scanf("%lld",&x);

			Ans+=x;

			add(pos(i,j),T,x);

		}

	id=n*m;

	for(int i=1;i<n;++i)

		for(int j=1;j<=m;++j){

			int P=build(),x;

			scanf("%lld",&x);

			Ans+=x;

			add(S,P,x);

			add(P,pos(i,j),inf);

			add(P,pos(i+1,j),inf);

		}

	for(int i=1;i<n;++i)

		for(int j=1;j<=m;++j){

			int x,P=build();

			scanf("%lld",&x);

			Ans+=x;

			add(P,T,x);

			add(pos(i,j),P,inf);

			add(pos(i+1,j),P,inf);

		}

	for(int i=1;i<=n;++i)

		for(int j=1;j<m;++j){

			int P=build(),x;

			scanf("%lld",&x);

			Ans+=x;

			add(S,P,x);

			add(P,pos(i,j),inf);

			add(P,pos(i,j+1),inf);

		}

	for(int i=1;i<=n;++i)

		for(int j=1;j<m;++j){

			int P=build(),x;

			scanf("%lld",&x);

			Ans+=x;

			add(P,T,x);

			add(pos(i,j),P,inf);

			add(pos(i,j+1),P,inf);

		}

	printf("%lld\n",Ans-dinic(S,T));

	return 0;

}

巴特西

【题解】[国家集训队]happiness

最新文章

热门文章