看到这张图，是一个网格图，而且有回路限制，不难想到黑白染色。
一般来说我们对一张图黑白染色之后都是黑色点向白色点连边，但是这道题往这边想似乎就想不出建图方法了，因为“一个格子强制流满(2)的流”和“权值和最大”无法同时在这张图上体现出来。
实际上这道题黑色和白色、白色和黑色之间都需要连边。
我们令左右方向的管道全部从黑色向白色连，上下方向的管道全部从白色往黑色连。也就是对于每一个点拆成入点和出点，对于黑色的入点，向其左右方向的白色出点连边；对于白色的入点，向其上下方向的黑色出点连边。连边的容量为(1)、费用为管道的价值。
然后考虑强制选择的限制。对于某个点，如果它没有被强制限制，就将其入点和出点之间连一条容量为(1)、费用为(0)的边，表示它能够自己和自己匹配。
这样就可以跑最大费用最大流了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
#include<random>
#include<cassert>
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;
const int MAXN = 1e5 + 7 , MAXM = 1e6 + 7;
struct Edge{
int end , upEd , f , c;
}Ed[MAXM];
int head[MAXN] , val[32][32][2] , id[32][32][2];
int N , M , S , T , cntEd = 1;
bool mrk[32][32];
queue < int > q;
inline void addEd(int a , int b , int c , int d = 0){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].f = c;
Ed[cntEd].c = d;
head[a] = cntEd;
}
inline void addE(int a , int b , int c , int d = 0 , bool f = 0){
addEd(a , b , c , d); addEd(b , a , c * f , -d);
}
bool vis[MAXN];
int dis[MAXN] , pre[MAXN] , flo[MAXN];
inline bool SPFA(){
memset(dis , -0x3f , sizeof(dis));
dis[S] = 0;
while(!q.empty())
q.pop();
q.push(S);
flo[S] = INF;
while(!q.empty()){
int t = q.front();
q.pop();
vis[t] = 0;
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(Ed[i].f && dis[Ed[i].end] < dis[t] + Ed[i].c){
dis[Ed[i].end] = dis[t] + Ed[i].c;
flo[Ed[i].end] = min(Ed[i].f , flo[t]);
pre[Ed[i].end] = i;
if(!vis[Ed[i].end]){
vis[Ed[i].end] = 1;
q.push(Ed[i].end);
}
}
}
return dis[T] != dis[T + 1];
}
int EK(){
int ans = 0 , flow = 0;
while(SPFA()){
int cur = T , sum = 0;
while(cur != S){
sum += Ed[pre[cur]].c;
Ed[pre[cur]].f -= flo[T];
Ed[pre[cur] ^ 1].f += flo[T];
cur = Ed[pre[cur] ^ 1].end;
}
flow += flo[T];
ans += sum * flo[T];
}
return flow == N * M ? ans : -1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
ios::sync_with_stdio(0);
int t , E , x , y , Case = 0;
for(cin >> t ; t ; --t){
cin >> N >> M;
T = 0; cntEd = 1;
memset(head , 0 , sizeof(head));
memset(mrk , 0 , sizeof(mrk));
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= M ; ++j){
id[i][j][0] = ++T; id[i][j][1] = ++T;
}
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j < M ; ++j){
cin >> x;
if(!((i + j) & 1)) val[i][j][1] = x;
else val[i][j + 1][0] = x;
}
for(int i = 1 ; i < N ; ++i)
for(int j = 1 ; j <= M ; ++j){
cin >> x;
if((i + j) & 1) val[i][j][1] = x;
else val[i + 1][j][0] = x;
}
++T;
for(cin >> E ; E ; --E){cin >> x >> y; mrk[x][y] = 1;}
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= M ; ++j){
addE(S , id[i][j][0] , 1);
addE(id[i][j][1] , T , 1);
if(!mrk[i][j]) addE(id[i][j][0] , id[i][j][1] , 1);
if((i + j) & 1){
if(i != 1)
addE(id[i][j][0] , id[i - 1][j][1] , 1 , val[i][j][0]);
if(i != N)
addE(id[i][j][0] , id[i + 1][j][1] , 1 , val[i][j][1]);
}
else{
if(j != 1)
addE(id[i][j][0] , id[i][j - 1][1] , 1 , val[i][j][0]);
if(j != M)
addE(id[i][j][0] , id[i][j + 1][1] , 1 , val[i][j][1]);
}
}
int t = EK();
cout << "Case #" << ++Case << ": ";
if(t == -1) cout << "Impossible
";
else cout << t << '
';
}
return 0;
}