打卡第十一天 P1646 [国家集训队] happiness

今天是我打卡第十一天，做个省选/NOI−题吧(#^.^#)

原题链接：[国家集训队] happiness - 洛谷

题目描述

高一一班的座位表是个 n×m 的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。

作为计算机竞赛教练的 scp 大老板，想知道如何分配可以使得全班的喜悦值总和最大。

输入格式

第一行两个正整数 n，m。

接下来是六个矩阵。

第一个矩阵为 n 行 m 列。此矩阵的第 i 行第 j列的数字表示座位在第 i 行第 j 列的同学选择文科获得的喜悦值。
第二个矩阵为 n 行 m 列。此矩阵的第 i行第 j 列的数字表示座位在第 i行第 j 列的同学选择理科获得的喜悦值。
第三个矩阵为 n−1 行 m 列。此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j列的同学与第 i+1行第 j 列的同学同时选择文科获得的额外喜悦值。
第四个矩阵为 n−1 行 m 列。此矩阵的第 i 行第 j 列的数字表示座位在第 i 行第 j 列的同学与第 i+1行第 j列的同学同时选择理科获得的额外喜悦值。
第五个矩阵为 n 行 m−1 列。此矩阵的第 i 行第 j列的数字表示座位在第 i 行第 j 列的同学与第 i 行第 j+1列的同学同时选择文科获得的额外喜悦值。
第六个矩阵为 n行m−1 列。此矩阵的第 i 行第 j列的数字表示座位在第 i 行第 j 列的同学与第 i 行第j+1 列的同学同时选择理科获得的额外喜悦值。

输出格式

输出一个整数，表示喜悦值总和的最大值。

输入输出样例

输入 #1

输出 #1

说明/提示

样例解释

两人都选理，则获得100+110+1000 的喜悦值。

对于100% 的数据，1≤n,m≤100，且所有喜悦值均为小于等于5000 的非负整数。

题解：

top1（由洛谷用户Siyuan提供）

Description

题目链接：Luogu 1646

作为计算机竞赛教练的 scp 大老板，想知道如何分配可以使得全班的喜悦值总和最大。

数据范围：1≤n,m≤100，喜悦值均为小于等于5000 的非负整数。

Solution

考虑用网络流求解，总量减去最小割即为答案。

对于每个点 (i,j)，从 s 连一条容量为选择文科的边，到 t 连一条容量位选择理科的边。

对于(i,j) 和 (i+1,j) 两个点的组合情况。假设这两个点同时选文科有 w 的喜悦值，我们新建一个节点 x，从 s 向 x 连一条容量为喜悦值 w 的边，再从 x 向 (i,j) 和(i+1,j) 分别连一条容量为 INF 的边。对于左右前后、文科理科同理！

考虑这样做法的正确性：每个点自然只能选择一个科目（文科或理科），当某个点选择了文科 s，那么它向理科 t 的边都应该要被断开。考虑哪些边会被断开：首先是它直接连向 t 的边，其次是它和别的点组合连向 t 的边，这样一来，这些边在网络图的割中是有贡献的，意味着这些边的容量在答案中没有贡献，正确性证明完毕。

时间复杂度：O((nm)^3)（Dinic）

Code

#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;
}

top2（由洛谷用户Dispwnl提供）

思路

考虑记录总量再求最小割

对于每个点，SS（源点）与ta连一条容量为选文的边，TT（汇点）与ta连一条容量为选理的边

建立新节点，SS与新节点连一条容量为前后桌同时选文的边

新节点再分别与前后桌连一条容量为infinf的边（为了不影响答案）

再建一个新节点，新节点与t连一条容量为前后桌同时选理的边

前后桌再与新节点连一条容量为infinf的边

左右桌同理

这时跑最小割（也就是最大流），得到的是最小得不到的快乐值

所以所有快乐值-最小割就是答案

样例的图：

图中红点为第一个新建的点，橙点为第二个新建的点，蓝点为原来的点，跑最小割为33

代码

# include<iostream>
# include<cstdio>
# include<cstring>
# include<cstdlib>
# include<queue>
# define pu(x,y) (x-1)*m+y
using namespace std;
const int MAX=2e5+1,inf=1e8,t=2e5;
struct p{int x,y,dis;
}c[MAX<<1];
int n,m,num,SUM;
int h[MAX],d[MAX];
void add(int x,int y,int dis)
{c[num].x=h[y],c[num].y=x,c[num].dis=0,h[y]=num++;c[num].x=h[x],c[num].y=y,c[num].dis=dis,h[x]=num++;
}
bool bfs()
{memset(d,0,sizeof(d));queue<int> qu;qu.push(0);d[0]=1;while(!qu.empty()){int tt=qu.front();qu.pop();for(int i=h[tt];i;i=c[i].x)if(!d[c[i].y]&&c[i].dis){d[c[i].y]=d[tt]+1;qu.push(c[i].y);}}return d[t];
}
int dfs(int x,int dix)
{if(!dix||x==t) return dix;int sum=0;for(int i=h[x];i;i=c[i].x)if(c[i].dis&&d[c[i].y]==d[x]+1){int dis=dfs(c[i].y,min(dix,c[i].dis));if(dis){dix-=dis;sum+=dis;c[i].dis-=dis;c[i^1].dis+=dis;if(!dix) break;}}if(!sum) d[x]=-1;return sum;
}
int dinic()
{int tot=0;while(bfs()) tot+=dfs(0,inf);return tot;
}
int main()
{scanf("%d%d",&n,&m);int ss=pu(n,m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int dis,tt=pu(i,j);scanf("%d",&dis);SUM+=dis;add(0,tt,dis);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int dis,tt=pu(i,j);scanf("%d",&dis);SUM+=dis;add(tt,t,dis);}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){int dis,tt=pu(i,j)+ss,t1=pu(i,j),t2=pu(i+1,j);scanf("%d",&dis);SUM+=dis;add(0,tt,dis);add(tt,t1,inf);add(tt,t2,inf);}for(int i=1;i<n;i++)for(int j=1;j<=m;j++){int dis,tt=pu(i,j)+2*ss,t1=pu(i,j),t2=pu(i+1,j);scanf("%d",&dis);SUM+=dis;add(tt,t,dis);add(t1,tt,inf);add(t2,tt,inf);}for(int i=1;i<=n;i++)for(int j=1;j<m;j++){int dis,tt=pu(i,j)+3*ss,t1=pu(i,j),t2=pu(i,j+1);scanf("%d",&dis);SUM+=dis;add(0,tt,dis);add(tt,t1,inf);add(tt,t2,inf);}for(int i=1;i<=n;i++)for(int j=1;j<m;j++){int dis,tt=pu(i,j)+4*ss,t1=pu(i,j),t2=pu(i,j+1);scanf("%d",&dis);SUM+=dis;add(tt,t,dis);add(t1,tt,inf);add(t2,tt,inf);}printf("%d",SUM-dinic());return 0;
}

top3（由洛谷用户Infiltrator提供）

Description

题目传送门

Solution

一种列方程的套路。

我们先单独找出两个点的关系来考虑。

假设有x和y两个同学，向S连边代表选理科，向T连边代表选文科。设S向x连的有向边为a，S向y连的有向边为b，xx向TT连的有向边为c，y向T连的有向边为d，x和y之间连了一条双向边e，割掉一条边的流量代表损失了这么多的愉悦值。

设都选理科的愉悦值是v1，都选文科的愉悦值是v2，按照题意可列方程组如下：

a+b=v1

这是对应的两个同学都选理科。

c+d=v2

这是对应的两个同学都选文科。

a+e+d=v1+v2

这是对应的x选理科，y选文科。

b+e+c=v1+v2

这是对应的xx选文科，yy选理科。

解得

那么我们只需要从S向每个点连一条容量为该同学选理科的愉悦值和他所有相邻的同学选理科的之和的有向边，从每个同学向TT连一条容量为该同学选文科和他所有相邻的同学都选文科的愉悦值之和的有向边。

每个同学向它相邻的同学连一条容量为他们同时都选理科或者文科的愉悦值的平均值的双向边。

那么答案就是所有愉悦值的和减去最小割。

注意因为要算平均值，所以可能出现小数，这样在一开始连边的时候乘二，最后再除以二就行了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue> 
using namespace std;const int N = 1000050;
const int M = 2000050;
const int INF = 999999999;int head[N], num = 1, n, m, s, t, tu[500][500][2], tmp[500][500], sum, d[N], x;struct Node
{int next, to, flow;
} edge[M * 2];void Addedge(int u, int v, int w)
{edge[++num] = (Node){head[u], v, w};head[u] = num;return;
}void Add(int u, int v, int w)
{Addedge(u, v, w);Addedge(v, u, 0);return;
}int Id(int a, int b)
{return (a - 1) * m + b;
} template <class T>
void Read(T &x)
{x = 0; int p = 0; char st = getchar();while (st < '0' || st > '9') p = (st == '-'), st = getchar();while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) +st - '0', st = getchar();	x = p ? -x : x;return;
} template <class T>
void Put(T x)
{if (x < 0) putchar('-'), x = -x;if (x > 9) Put(x / 10);putchar(x % 10 + '0');return; 
}bool Bfs()
{queue<int> q;for (int i = 0; i <= t; i++) d[i] = 0;d[s] = 1; q.push(s);while (!q.empty()){int u = q.front(); q.pop();for (int i = head[u]; i; i = edge[i].next)if (!d[edge[i].to] && edge[i].flow){d[edge[i].to] = d[u] + 1;q.push(edge[i].to);if (edge[i].to == t) return 1;}}return 0;
}int Dinic(int x, int flow)
{if (x == t || !flow) return flow;int rest = flow;for (int i = head[x]; i && rest; i = edge[i].next)if (edge[i].flow && d[edge[i].to] == d[x] + 1){int v = edge[i].to;int tmp = Dinic(v, min(rest, edge[i].flow));rest -= tmp;edge[i].flow -= tmp;edge[i ^ 1].flow += tmp;if (!tmp) d[v] = 0;}return flow - rest;
}int Maxflow()
{int maxflow = 0, tmp;while (Bfs()){tmp = Dinic(s, INF);if (tmp) maxflow += tmp;}return maxflow;
}int main()
{Read(n); Read(m); t = n * m + 1;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){Read(x);sum += x;tu[i][j][1] += x * 2;}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){Read(x);sum += x;tu[i][j][0] += x * 2;}for (int i = 1; i <= n - 1; i++)for (int j = 1; j <= m; j++){Read(x);sum += x;tmp[i][j] += x;tu[i][j][1] += x;tu[i + 1][j][1] += x;}for (int i = 1; i <= n - 1; i++)for (int j = 1; j <= m; j++){Read(x);sum += x;tmp[i][j] += x;Add(Id(i, j), Id(i + 1, j), tmp[i][j]);Add(Id(i + 1, j), Id(i, j), tmp[i][j]);tu[i][j][0] += x;tu[i + 1][j][0] += x;tmp[i][j] = 0;}for (int i = 1; i <= n; i++)for (int j = 1; j <= m - 1; j++){Read(x);sum += x;tmp[i][j] += x;tu[i][j][1] += x;tu[i][j + 1][1] += x; }for (int i = 1; i <= n; i++)for (int j = 1; j <= m - 1; j++){Read(x);sum += x;tmp[i][j] += x;Add(Id(i, j), Id(i, j + 1), tmp[i][j]);Add(Id(i, j + 1), Id(i, j), tmp[i][j]);tu[i][j][0] += x;tu[i][j + 1][0] += x;}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){Add(s, Id(i, j), tu[i][j][0]);Add(Id(i, j), t, tu[i][j][1]);}Put(sum - Maxflow() / 2); return 0;
}