高一一班的座位表是个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 2 1 1 100 110 1 1000
1210 【样例说明】 两人都选理,则获得100+110+1000的喜悦值。 【数据规模】 对于100%以内的数据,n,m<=100 所有喜悦值均为小于等于5000的非负整数
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 using namespace std;
7 const int MAXN=200001;
8 const int INF = 1e8;
9 inline void read(int &n)
10 {
11 char c='+';int x=0;bool flag=0;
12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
13 while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
14 n=flag==1?-x:x;
15 }
16 int n,m,s,t;
17 struct node
18 {
19 int u,v,flow,nxt;
20 }edge[MAXN];
21 int head[MAXN];
22 int cur[MAXN];
23 int num=0;
24 int deep[MAXN];
25 int tot=0;
26 void add_edge(int x,int y,int z)
27 {
28 edge[num].u=x;
29 edge[num].v=y;
30 edge[num].flow=z;
31 edge[num].nxt=head[x];
32 head[x]=num++;
33 }
34 void add(int x,int y,int z)
35 {
36 add_edge(x,y,z);
37 add_edge(y,x,0);
38 }
39 bool BFS()
40 {
41 memset(deep,0,sizeof(deep));
42 deep[s]=1;
43 queue<int>q;
44 q.push(s);
45 while(q.size()!=0)
46 {
47 int p=q.front();
48 q.pop();
49 for(int i=head[p];i!=-1;i=edge[i].nxt)
50 if(!deep[edge[i].v]&&edge[i].flow)
51 deep[edge[i].v]=deep[edge[i].u]+1,
52 q.push(edge[i].v);
53 }
54 return deep[t];
55
56 }
57 int DFS(int now,int nowflow)
58 {
59 if(now==t||nowflow<=0)
60 return nowflow;
61 int totflow=0;
62 for(int &i=cur[now];i!=-1;i=edge[i].nxt)
63 {
64 if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow)
65 {
66 int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
67 edge[i].flow-=canflow;
68 edge[i^1].flow+=canflow;
69 totflow+=canflow;
70 nowflow-=canflow;
71 if(nowflow<=0)
72 break;
73 }
74
75 }
76 return totflow;
77 }
78 void Dinic()
79 {
80 int ans=0;
81 while(BFS())
82 {
83 memcpy(cur,head,MAXN);
84 ans+=DFS(s,1e8);
85 }
86 printf("%d",tot-(ans>>1));
87 }
88 int a[101][101];
89 int b[101][101];
90 int mark[101][101];
91 int main()
92 {
93 int n,m;
94 read(n);read(m);
95 s=0;t=10001;
96 memset(head,-1,sizeof(head));
97 for(int i=1;i<=n;i++)
98 for(int j=1;j<=m;j++)
99 cin>>a[i][j],tot+=a[i][j],a[i][j]<<=1;
100 for(int i=1;i<=n;i++)
101 for(int j=1;j<=m;j++)
102 cin>>b[i][j],tot+=b[i][j],b[i][j]<<=1;
103 for(int i=1;i<=n;i++)
104 for(int j=1;j<=m;j++)
105 mark[i][j]=((i-1)*m+j);
106 for(int i=1;i<=n-1;i++)
107 for(int j=1;j<=m;j++)
108 {
109 int p;cin>>p;tot+=p;
110 a[i][j]+=p,a[i+1][j]+=p;
111 add_edge(mark[i][j],mark[i+1][j],p);
112 add_edge(mark[i+1][j],mark[i][j],p);
113 }
114 for(int i=1;i<=n-1;i++)
115 for(int j=1;j<=m;j++)
116 {
117 int p;cin>>p;tot+=p;
118 b[i][j]+=p,b[i+1][j]+=p;
119 add_edge(mark[i][j],mark[i+1][j],p);
120 add_edge(mark[i+1][j],mark[i][j],p);
121 }
122 for(int i=1;i<=n;i++)
123 for(int j=1;j<=m-1;j++)
124 {
125 int p;cin>>p;tot+=p;
126 a[i][j]+=p,a[i][j+1]+=p;
127 add_edge(mark[i][j],mark[i][j+1],p);
128 add_edge(mark[i][j+1],mark[i][j],p);
129 }
130 for(int i=1;i<=n;i++)
131 for(int j=1;j<=m-1;j++)
132 {
133 int p;cin>>p;tot+=p;
134 b[i][j]+=p,b[i][j+1]+=p;
135 add_edge(mark[i][j],mark[i][j+1],p);
136 add_edge(mark[i][j+1],mark[i][j],p);
137 }
138 for(int i=1;i<=n;i++)
139 for(int j=1;j<=m;j++)
140 {
141 add(0,mark[i][j],a[i][j]);
142 add(mark[i][j],t,b[i][j]);
143 }
144 Dinic();
145 return 0;
146 }