高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。
作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。
$S$对每个点连选文的收益, 每个点向$T$连选理的收益. 相邻点选文的收益只需要再开一个点$x$, $S$连向$x$容量为收益, $x$连向对应点容量无穷. 相邻点选理同理.
最后用总收益减去最小割即为答案.
#include <iostream> #include <cstdio> #include <queue> #include <map> #define REP(i,a,n) for(int i=a;i<=n;++i) using namespace std; typedef pair<int,int> pii; inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;} const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f; int n, m, tot, sum; map<pii,int> mp; int ID(int i, int j) { if (mp.count(pii(i,j))) return mp[pii(i,j)]; return mp[pii(i,j)] = ++tot; } struct edge { int to,w,next; edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){} } e[N]; int head[N], dep[N], vis[N], cur[N], cnt=1; queue<int> Q; int bfs() { REP(i,1,tot) dep[i]=INF,vis[i]=0,cur[i]=head[i]; dep[S]=INF,vis[S]=0,cur[S]=head[S]; dep[T]=INF,vis[T]=0,cur[T]=head[T]; dep[S]=0,Q.push(S); while (Q.size()) { int u = Q.front(); Q.pop(); for (int i=head[u]; i; i=e[i].next) { if (dep[e[i].to]>dep[u]+1&&e[i].w) { dep[e[i].to]=dep[u]+1; Q.push(e[i].to); } } } return dep[T]!=INF; } int dfs(int x, int w) { if (x==T) return w; int used = 0; for (int i=cur[x]; i; i=e[i].next) { cur[x] = i; if (dep[e[i].to]==dep[x]+1&&e[i].w) { int f = dfs(e[i].to,min(w-used,e[i].w)); if (f) used+=f,e[i].w-=f,e[i^1].w+=f; if (used==w) break; } } return used; } int dinic() { int ans = 0; while (bfs()) ans+=dfs(S,INF); return ans; } void add(int u, int v, int w) { if (w!=INF) sum += w; e[++cnt] = edge(v,w,head[u]); head[u] = cnt; e[++cnt] = edge(u,0,head[v]); head[v] = cnt; } int main() { scanf("%d%d", &n, &m); REP(i,1,n) REP(j,1,m) add(S,ID(i,j),rd()); REP(i,1,n) REP(j,1,m) add(ID(i,j),T,rd()); REP(i,1,n-1) REP(j,1,m) { add(S,ID(i+n,j),rd()); add(ID(i+n,j),ID(i,j),INF); add(ID(i+n,j),ID(i+1,j),INF); } REP(i,1,n-1) REP(j,1,m) { add(ID(i+2*n,j),T,rd()); add(ID(i,j),ID(i+2*n,j),INF); add(ID(i+1,j),ID(i+2*n,j),INF); } REP(i,1,n) REP(j,1,m-1) { add(S,ID(i+3*n,j),rd()); add(ID(i+3*n,j),ID(i,j),INF); add(ID(i+3*n,j),ID(i,j+1),INF); } REP(i,1,n) REP(j,1,m-1) { add(ID(i+4*n,j),T,rd()); add(ID(i,j),ID(i+4*n,j),INF); add(ID(i,j+1),ID(i+4*n,j),INF); } printf("%d ", sum-dinic()); }