有一种限制下界强制选的，但是也可以不用
把每个格点拆成两个，一个连s一个连t，对于不是必选的连中间连流量1费用0边表示不选，然后黑白染色，黑点连横着白点连竖着，边权就是这条水管的权值，然后跑最大费用最大流
然后判断不可能就是不满流
并且这样可以满足每个被选的格子都在一个环上，因为他一定唯一对应另一个唯一的点，也就是出入度都是1
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=2005;
int T,n,m,k,cas,vh[N][N],vs[N][N],idb[N][N],idw[N][N],tot,s,t,h[N],cnt,fr[N],dis[N],ans,sm;
bool v[N],a[N][N];
struct qwe
{
int ne,no,to,va,c;
}e[N*N];
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
void add(int u,int v,int w,int c)
{
cnt++;
e[cnt].ne=h[u];
e[cnt].no=u;
e[cnt].to=v;
e[cnt].va=w;
e[cnt].c=c;
h[u]=cnt;
}
void ins(int u,int v,int w,int c)
{
add(u,v,w,c);
add(v,u,0,-c);
}
bool spfa()
{
for(int i=s;i<=t;i++)
dis[i]=-1e9;
queue<int>q;
q.push(s);
v[s]=1;
dis[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
v[u]=0;
for(int i=h[u];i;i=e[i].ne)
if(e[i].va>0&&dis[e[i].to]<dis[u]+e[i].c)
{
dis[e[i].to]=dis[u]+e[i].c;
fr[e[i].to]=i;
if(!v[e[i].to])
{
v[e[i].to]=1;
q.push(e[i].to);
}
}
}
return dis[t]!=-1e9;
}
void mcf()
{
int x=1e9;
for(int i=fr[t];i;i=fr[e[i].no])
x=min(x,e[i].va);
sm+=x;
for(int i=fr[t];i;i=fr[e[i].no])
{
e[i].va-=x;
e[i^1].va+=x;
ans+=e[i].c*x;
}
}
int main()
{
T=read();
while(T--)
{
memset(h,0,sizeof(h));
memset(a,0,sizeof(a));
cnt=1,tot=0,ans=0,sm=0;
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
vh[i][j]=read();
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
vs[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
idb[i][j]=++tot,idw[i][j]=++tot;
s=0,t=tot+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if((i+j)&1)
{
if(j+1<=m)
ins(idb[i][j],idw[i][j+1],1,vh[i][j]);
if(j-1>=1)
ins(idb[i][j],idw[i][j-1],1,vh[i][j-1]);
}
else
{
if(i+1<=n)
ins(idb[i][j],idw[i+1][j],1,vs[i][j]);
if(i+1>=1)
ins(idb[i][j],idw[i-1][j],1,vs[i-1][j]);
}
}
k=read();
for(int i=1;i<=k;i++)
{
int x=read(),y=read();
a[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
ins(s,idb[i][j],1,0);
ins(idw[i][j],t,1,0);
if(!a[i][j])
ins(idb[i][j],idw[i][j],1,0);
}
while(spfa())
mcf();
if(sm<n*m)
printf("Case #%d: Impossible
",++cas);
else
printf("Case #%d: %d
",++cas,ans);
}
return 0;
}
/*
2
4 4
0 0 -1
0 1 0
0 -1 -1
0 1 0
1 0 1 0
-1 -1 0 0
1 1 -1 -1
1
3 3
2 3
0 0
0 0
0 0 0
2
1 1
2 3
*/