传送门

---

看到这张图，是一个网格图，而且有回路限制，不难想到黑白染色。

一般来说我们对一张图黑白染色之后都是黑色点向白色点连边，但是这道题往这边想似乎就想不出建图方法了，因为“一个格子强制流满\(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\n";

		else cout << t << '\n';

	}

	return 0;

}