command_block 的博客

command_block 的博客

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

posted on 2021-10-29 19:54:19 | under 记录 |

题意 : 给出一个 $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)$ 。

#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;
}