happiness

发表于 | 分类于

题目

传送门
高一一班的座位表是个n×m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。

INPUT

第一行两个正整数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列的同学同时选择理科获得的额外喜悦值。

OUTPUT

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

SAMPLE

INPUT

1 2
1 1
100 110
1
1000

OUTPUT

1210

解题报告

选择不同时不能得到额外的权值，所以源点对所有点来说都是文科，汇点对所有点来说都是理科。
对于单独两个点来说，只有两种情况。
若两个人都选文科，需要割掉第2，4条边，代价为两个人选理科分别的贡献，以及他们一起选理科的贡献，因为所有的点都是等价的，2，4边的权值除各自选理科贡献外再加上一半的额外贡献。
若两个人都选择理科同理。
若两个人选择不同，假设x选择文科，y选择理科，那么需要割掉2，3，5。
此时2，3权值和为分别选择科目的贡献和一半的同时选择理科和同时选择文科的贡献。还需再减去剩余的一半，即应是5的权值。(x，y间要建双向边。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[200001];
int pre[10010],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int n,m;
int w[101][101],l[101][101];
int jz1[101][101],jz2[101][101],jz3[101][101],jz4[101][101];
int sum(0),ans(0),inf(0x7fffffff);
int S(0),T;
int id[101][101];
inline void init(){
	freopen("nt2011_happiness.in","r",stdin);
	freopen("nt2011_happiness.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),m=read();
	T=n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			w[i][j]=read()<<1,sum+=w[i][j]>>1,id[i][j]=(i-1)*m+j;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			l[i][j]=read()<<1,sum+=l[i][j]>>1;
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			jz1[i][j]=read(),sum+=jz1[i][j];
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			jz2[i][j]=read(),sum+=jz2[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			jz3[i][j]=read(),sum+=jz3[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			jz4[i][j]=read(),sum+=jz4[i][j];
}
inline void build(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			insert(S,id[i][j],w[i][j]+jz1[i][j]+jz1[i-1][j]+jz3[i][j]+jz3[i][j-1]),insert(id[i][j],S,0);
			insert(id[i][j],T,l[i][j]+jz2[i][j]+jz2[i-1][j]+jz4[i][j]+jz4[i][j-1]),insert(T,id[i][j],0);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(i!=n)
				insert(id[i][j],id[i][j]+m,jz1[i][j]+jz2[i][j]),insert(id[i][j]+m,id[i][j],jz1[i][j]+jz2[i][j]);
			if(j!=m)
				insert(id[i][j],id[i][j]+1,jz3[i][j]+jz4[i][j]),insert(id[i][j]+1,id[i][j],jz3[i][j]+jz4[i][j]);
		}
}
int dis[10020];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
}
inline void dinic(){
	while(bfs(S,T))
		ans+=dfs(S,inf);
	printf("%d",sum-(ans>>1));
}
inline int gg(){
	init();
	build();
	dinic();
	return 0;
}
int K(gg());
int main(){;}