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

[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/) --- ## Description > 题目链接：[Luogu 1646](https://www.luogu.org/problemnew/show/P1646) 高一一班的座位表是个 $n\times m$ 的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。 作为计算机竞赛教练的 scp 大老板，想知道如何分配可以使得全班的喜悦值总和最大。 数据范围：$1\le n,m\le 100$，喜悦值均为小于等于 $5000$ 的非负整数。 ------ ## Solution 考虑用网络流求解，**总量减去最小割**即为答案。 对于每个点 $(i,j)$，从 $s$ 连一条容量为选择文科的边，到 $t$ 连一条容量位选择理科的边。 对于 $(i,j)$ 和 $(i+1,j)$ 两个点的组合情况。假设这两个点同时选文科有 $w$ 的喜悦值，我们新建一个节点 $x$，从 $s$ 向 $x$ 连一条容量为喜悦值 $w$ 的边，再从 $x$ 向 $(i,j)$ 和 $(i+1,j)$ 分别连一条容量为 $\texttt{INF}$ 的边。对于左右前后、文科理科同理！ 考虑这样做法的**正确性**：每个点自然只能选择一个科目（文科或理科），当某个点选择了文科 $s$，那么它向理科 $t$ 的边都应该要被断开。考虑哪些边会被断开：首先是它直接连向 $t$ 的边，其次是它和别的点组合连向 $t$ 的边，这样一来，这些边在网络图的**割**中是有贡献的，意味着这些边的容量在答案中没有贡献，正确性证明完毕。 **时间复杂度**：$O((nm)^3)$（$\texttt{Dinic}$） ------ ## Code ```cpp #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define FOR(i,a,b) for(int i=a;i<=b;++i) const int N=1e5+5,M=5e6+5; const int inf=1<<30; int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N]; int id(int x,int y) { return (x-1)*m+y; } void add(int u,int v,int w) { ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w; } void addedge(int u,int v,int w) { add(u,v,w),add(v,u,0); } int bfs(int s,int t) { memset(dep,0,sizeof(dep)); memcpy(cnr,lnk,sizeof(lnk)); std::queue<int> q; q.push(s),dep[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=lnk[u];i;i=nxt[i]) { int v=ter[i]; if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1; } } return dep[t]; } int dfs(int u,int t,int flow) { if(u==t) return flow; int ans=0; for(int i=cnr[u];i&&ans<flow;i=nxt[i]) { cnr[u]=i; int v=ter[i]; if(val[i]&&dep[v]==dep[u]+1) { int x=dfs(v,t,std::min(val[i],flow-ans)); if(x) val[i]-=x,val[i^1]+=x,ans+=x; } } if(ans<flow) dep[u]=-1; return ans; } int dinic(int s,int t) { int ans=0; while(bfs(s,t)) { int x; while((x=dfs(s,t,inf))) ans+=x; } return ans; } int main() { scanf("%d%d",&n,&m); int s=0,t=n*m+2*n*(m-1)+2*(n-1)*m+1,cnt=n*m; int ans=0; FOR(i,1,n) FOR(j,1,m) { int x; scanf("%d",&x),ans+=x; addedge(s,id(i,j),x); } FOR(i,1,n) FOR(j,1,m) { int x; scanf("%d",&x),ans+=x; addedge(id(i,j),t,x); } FOR(i,1,n-1) FOR(j,1,m) { int x; scanf("%d",&x),ans+=x; addedge(s,++cnt,x); addedge(cnt,id(i,j),inf); addedge(cnt,id(i+1,j),inf); } FOR(i,1,n-1) FOR(j,1,m) { int x; scanf("%d",&x),ans+=x; addedge(++cnt,t,x); addedge(id(i,j),cnt,inf); addedge(id(i+1,j),cnt,inf); } FOR(i,1,n) FOR(j,1,m-1) { int x; scanf("%d",&x),ans+=x; addedge(s,++cnt,x); addedge(cnt,id(i,j),inf); addedge(cnt,id(i,j+1),inf); } FOR(i,1,n) FOR(j,1,m-1) { int x; scanf("%d",&x),ans+=x; addedge(++cnt,t,x); addedge(id(i,j),cnt,inf); addedge(id(i,j+1),cnt,inf); } printf("%d\n",ans-dinic(s,t)); return 0; } ```