[图论记录]P7916 [CSP-S 2021] 交通规划（民间数据）

**题意** ： 给出一个 $n\times m$ 的网格图，边有边权。 有 $T$ 次询问，每次询问给出 $k_i$ 个**网格边界上**的点，给每个点建立一个新点，并连边，也给出边权。 建立新图后，需要将点黑白染色，使得一端黑一端白的边权和最小，回答这个最小值。 $n,m\leq 500,\sum k\leq 50$ ，时限$\texttt{3s}$。 ------------ 尽管维持了形式上的不超纲，以最小割为核心模型，网络流为大众暴力的本题，是命题的偶然，还是预示着新时代的开始呢？ 抛开这些试题的限制不谈，题目本身是很好的。学到许多。 - **最小割模型** 这个非常显然，熟练的选手可以发现，将“黑色”看做 $S$ 集，将“白色”看做 $T$ 集，则“黑白之间的边”恰好对应一种割。 - $k=2$ 此时图是平面图。**平面图的有源汇最小割可以转为对偶图上的最短路。** 观察下列图例：  左侧是一张平面图（加粗）与其对偶图（未加粗）。所谓对偶图就是将平面图的边围成的每个“区域”看做一个点，对于相邻区域之间的分界边，给这两个区域连边，边权为分界边的权值。 右侧是平面图上的割，以及对偶图上的对应边集（黑色）。不难发现，平面图上的一种割对应对偶图上的一条路径。 怎样的路径才分割 $S,T$ 两点？我们可以从 $S,T$ 向外发射射线，将无限大的区域分成两个部分，横跨两部分的一条路径即对应 $S,T$ 之间的一种割。 求个最短路就能得到最小割。 - $k>2$ 此时不太能用单源单汇最短路描述问题了。观察下图中割的分布：  我们按顺时针（逆时针也可）顺序，将网格周围相邻的红蓝点之前区域，交替地染成红色或蓝色。（也可以当做红先则红，蓝先则蓝） 不难发现，一组合法的割形如若干条连接红色区域和蓝色区域的路径，且每个区域恰好被连接一次。 先跑 $k$ 次 Dijkstra 求出这些区域两两的最短路。 发现匹配是不可能相交的，破环为链然后 $O(k^3)$ 区间 DP 即可求出最优匹配。 复杂度 $O(nmk\log nm+k^3)$ 。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define Pr pair<int,int> #define mp make_pair #define fir first #define sec second #define MaxG 255000 #define MaxN 505 #define MaxK 105 using namespace std; const int INF=1000000000; struct Line{int t,l,nxt;}l[MaxG<<2]; int fir[MaxG],tl; void adl(int u,int v,int len){ l[++tl]=(Line){v,len,fir[u]};fir[u]=tl; l[++tl]=(Line){u,len,fir[v]};fir[v]=tl; } priority_queue<Pr> q; int mx,dis[MaxG]; void Dijk(int s) { for (int i=1;i<=mx;i++)dis[i]=INF; q.push(mp(dis[s]=0,s)); while(!q.empty()){ Pr now=q.top();q.pop(); if (dis[now.sec]!=-now.fir)continue; int u=now.sec; for (int i=fir[u],v;i;i=l[i].nxt) if (dis[v=l[i].t]>dis[u]+l[i].l){ dis[v]=dis[u]+l[i].l; q.push(mp(-dis[v],v)); } } } struct Data{int id,col;}p[MaxK]; bool cmp(const Data &A,const Data &B) {return A.id<B.id;} int n,m,down[MaxN][MaxN],right[MaxN][MaxN] ,k,tn,s[MaxK],cost[MaxK][MaxK],dp[MaxK][MaxK]; #define pos(x,y) ((x)*(m+1)+(y)+1) int pos2(int p){ if (p<=m)return pos(0,p); if (p<=m+n)return pos(p-m,m); if (p<=m+n+m)return pos(n,m+n+m-p); return pos(2*(n+m)-p,0); } void solve() { scanf("%d",&k); for (int i=0;i<=n;i++)down[i][0]=down[i][m]=0; for (int j=0;j<=m;j++)right[0][j]=right[n][j]=0; for (int i=1,x;i<=k;i++){ scanf("%d%d%d",&x,&p[i].id,&p[i].col); int j=p[i].id; if (j<=m)right[0][j-1]=x; else if (p[i].id<=n+m)down[j-m-1][m]=x; else if (p[i].id<=2*m+n)right[n][m+m+n-j]=x; else down[2*(n+m)-j][0]=x; } for (int i=0;i<n;i++) for (int j=0;j<=m;j++) adl(pos(i,j),pos(i+1,j),down[i][j]); for (int i=0;i<=n;i++) for (int j=0;j<m;j++) adl(pos(i,j),pos(i,j+1),right[i][j]); sort(p+1,p+k+1,cmp); p[k+1]=p[1];tn=0; for (int i=1;i<=k;i++) if (p[i].col!=p[i+1].col) s[++tn]=pos2(p[i].id); if (!tn){puts("0");return ;} mx=pos(n,m); for (int i=1;i<=tn;i++){ Dijk(s[i]); for (int j=1;j<=tn;j++) cost[i][j]=cost[i][j+tn]=cost[i+tn][j+tn]=dis[s[j]]; } for (int len=2;len<=tn;len+=2) for (int l=1;l+len-1<=tn+tn;l++){ int r=l+len-1; dp[l][r]=INF; for (int k=l+1;k<=r;k+=2) dp[l][r]=min(dp[l][r],dp[l+1][k-1]+dp[k+1][r]+cost[l][k]); } int ans=INF; for (int l=1;l<=tn;l++) ans=min(ans,dp[l][l+tn-1]); printf("%d\n",ans); tl=0;for (int i=1;i<=mx;i++)fir[i]=0; } int main() { int T;scanf("%d%d%d",&n,&m,&T); for (int i=1;i<n;i++) for (int j=0;j<m;j++) scanf("%d",&right[i][j]); for (int i=0;i<n;i++) for (int j=1;j<m;j++) scanf("%d",&down[i][j]); while(T--)solve(); return 0; } ```