考虑平面图转对偶图之后，实际上就是一个求最短路的过程，但是这只能解决 \(k=2\) 的问题。
我们考虑当 \(k>2\) 的时候怎么做？
发现如果我们割出了一个最小割，实际上就是将整个问题划分成两个子问题（虽然不再是环了）。对于两个子问题，我们依旧使用同样的方法处理，发现实质上就是一个区间 \(\text{dp}\) 的过程。
所以我们一开始暴力处理出所有颜色分界点两两之间的割，然后跑一个区间 \(\text{dp}\) 就行了？
感觉这个平面图转对偶图非常阴间啊。
我个人的写法感觉是蛮不错的。
#include<bits/stdc++.h>
using namespace std;
const int N=5e2+5,K=55;
const int INF=1e9+7;
int n,m,k,T;
struct Fuck{int w,p,x;}a[K];
bool cmp(Fuck a,Fuck b){return a.p<b.p;}
int id[N][N],tot=0;
int val1[N][N],val2[N][N],val3[N*4];
struct Edge{int nxt,to,val;}e[N*N*4];
int cur[N*N],fir[N*N],e_size,E_size;
void add(int u,int v,int w){
e[++e_size]=(Edge){cur[u],v,w},cur[u]=e_size;
}
void Add(int u,int v,int w){
e[++E_size]=(Edge){fir[u],v,w},fir[u]=E_size;
}
int bag[K*2],cnt=0;
int f[K*2][K*2],dis[K][N*N];
struct Data{int dis,u;};
bool operator > (Data a,Data b){return a.dis>b.dis;}
priority_queue<Data,vector<Data>,greater<Data> > q;
void dijkstra(int from,int tag){
for(int i=1;i<=tot;++i) dis[tag][i]=INF;
dis[tag][from]=0,q.push((Data){0,from});
while(!q.empty()){
Data u=q.top();q.pop();
if(u.dis>dis[tag][u.u]) continue;
for(int i=fir[u.u];i;i=e[i].nxt){
int v=e[i].to;if(dis[tag][v]<=u.dis+e[i].val) continue;
dis[tag][v]=u.dis+e[i].val,q.push((Data){dis[tag][v],v});
}
}
}
int main(){
cin>>n>>m>>T;
for(int i=1;i<n;++i){
for(int j=1;j<=m;++j)
scanf("%d",&val1[i][j]);
}
for(int i=1;i<=n;++i){
for(int j=1;j<m;++j)
scanf("%d",&val2[i][j]);
}
for(int i=0;i<=n;++i){
for(int j=0;j<=m;++j)
id[i][j]=++tot;
}
for(int i=1;i<n;++i){
for(int j=1;j<=m;++j){
add(id[i][j-1],id[i][j],val1[i][j]);
add(id[i][j],id[i][j-1],val1[i][j]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<m;++j){
add(id[i-1][j],id[i][j],val2[i][j]);
add(id[i][j],id[i-1][j],val2[i][j]);
}
}
while(T--){
cin>>k,E_size=e_size;
for(int i=1;i<=tot;++i) fir[i]=cur[i];
for(int i=1;i<=2*(n+m);++i) val3[i]=0;
for(int i=1;i<=k;++i){
scanf("%d%d%d",&a[i].w,&a[i].p,&a[i].x);
val3[a[i].p]=a[i].w;
}
for(int i=1;i<=2*(n+m);++i){
if(1<=i&&i<=m){
Add(id[0][i-1],id[0][i],val3[i]);
Add(id[0][i],id[0][i-1],val3[i]);
}
if(m+1<=i&&i<=m+n){
Add(id[i-m-1][m],id[i-m][m],val3[i]);
Add(id[i-m][m],id[i-m-1][m],val3[i]);
}
if(m+n+1<=i&&i<=2*m+n){
Add(id[n][2*m+n-i],id[n][2*m+n-i+1],val3[i]);
Add(id[n][2*m+n-i+1],id[n][2*m+n-i],val3[i]);
}
if(2*m+n+1<=i&&i<=2*(m+n)){
Add(id[2*(m+n)-i][0],id[2*(m+n)-i+1][0],val3[i]);
Add(id[2*(m+n)-i+1][0],id[2*(m+n)-i][0],val3[i]);
}
}
sort(a+1,a+1+k,cmp),cnt=0;
for(int i=1;i<k;++i){
if(a[i].x!=a[i+1].x){
if(1<=a[i].p&&a[i].p<=m) bag[++cnt]=id[0][a[i].p];
if(m+1<=a[i].p&&a[i].p<=m+n) bag[++cnt]=id[a[i].p-m][m];
if(m+n+1<=a[i].p&&a[i].p<=2*m+n) bag[++cnt]=id[n][2*m+n-a[i].p];
if(2*m+n+1<=a[i].p&&a[i].p<=2*(n+m)) bag[++cnt]=id[2*(m+n)-a[i].p][0];
}
}
if(a[k].x!=a[1].x){
if(1<=a[k].p&&a[k].p<=m) bag[++cnt]=id[0][a[k].p];
if(m+1<=a[k].p&&a[k].p<=m+n) bag[++cnt]=id[a[k].p-m][m];
if(m+n+1<=a[k].p&&a[k].p<=2*m+n) bag[++cnt]=id[n][2*m+n-a[k].p];
if(2*m+n+1<=a[k].p&&a[k].p<=2*(n+m)) bag[++cnt]=id[2*(m+n)-a[k].p][0];
}
if(!cnt){printf("0\n");continue;}
for(int i=1;i<=cnt;++i) dijkstra(bag[i],i);
for(int i=1;i<=cnt;++i) bag[i+cnt]=bag[i];
for(int i=1;i<=cnt*2;++i){
for(int j=i;j<=cnt*2;++j) f[i][j]=INF;
f[i][i+1]=dis[(i-1)%cnt+1][bag[i+1]];
}
for(int len=4;len<=cnt;len+=2){
for(int i=1,j=len;j<=cnt*2;++i,++j){
for(int c=i+1;c<j;c+=2)
f[i][j]=min(f[i][j],f[i][c]+f[c+1][j]);
f[i][j]=min(f[i][j],f[i+1][j-1]+dis[(i-1)%cnt+1][bag[j]]);
}
}
int res=INF;
for(int i=1;i<=cnt;++i) res=min(res,f[i][i+cnt-1]);
printf("%d\n",res);
}
}