[CSP-S 2021] 交通规划 题解
[CSP-S 2021] 交通规划 题解
对偶图网络流+区间 DP
CCF一到店，所有 OIer 便都看着他笑，有的故意的高声嚷道，“你的题一定又超纲了！”CCF睁大眼睛说，“你怎么这样凭空污人清白……”“什么清白？我去年 CSP T4 啥都不会，被吊着打。”CCF便涨红了脸，额上的青筋条条绽出，争辩道，“题难不能超纲……题难！……出题的事，能算超纲么？
去年的题现在才来补 qwq
还记得考前教练说绝对不可能考网络流，哈哈
考场上不知道在干什么，45 分的 \(k=2\) 都不会 qwq，wtcl
严格来说也没有超纲，毕竟代码里面只有最短路和 DP 嘛
Statement
P7916 [CSP-S 2021] 交通规划 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给定一个 \(n\times m(n\times m\le 500)\) 的网格图，边有非负边权。网格图外围有一层 \(2n+2m\) 个特殊点，特殊点仅和 相邻网格图上的点 有连边，最开始边权为 \(\rm 0\)。 \(q(q\le 50)\) 个询问，每个询问给定 \(k(\sum k\le 50)\) 个特殊点的对应的非负边权、位置、颜色（黑白），你可以决定网格图上的点的颜色，两个有边相连的点有值为边权的贡献当且仅当两个点颜色不同，最小化贡献和。
Solution
考虑一个 01 变量 \(x\)，将 $x=0 $ 视为其对应点与源点联通，\(x=1\) 视为与汇点联通。那么考虑最小割中每条边的贡献：对于形如 \((S,x,a)\) 的边，当且仅当 \(x\) 与汇点联通时这条边才会有 \(a\) 的贡献，于是可以将这条边的贡献记为 \(ax\) 。同理，形如 \((x,T,a)\) 的边可看成 \(a(1-x)\)，而形如 \((x,y,a)\) 的边则可看成 \(a(1-x)y\)。对于某些问题，我们可以将贡献拆成上述三种形式，便可以通过跑最小割求解。
——Bindir0
容易发现转对偶图之后 \(k=2\) 就是一个最小割的事情，dij 就可以了（边权非负）
k=2
#include
#define id(x,y) ((x)*(m+1)+(y))
#define pii pair
#define fi first
#define se second
using namespace std;
const int N = 505;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
int s=0,w=1; char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
bool cmin(int &a,int b){return a>b?a=b,1:0;}
struct Edg{
int nex,to,dis;
}edge[N*N*4];
struct Point{
int x,p,t;
}node[55];
int head[N*N],pos[N<<2],dis[N*N];
priority_queue,greater >q;
vectorEdge[N*N];
int n,m,T,elen;
bool vis[N*N];
void addedge(int u,int v,int w,int op=1){
if(op)Edge[u].push_back(pii(v,w));
edge[++elen]=(Edg){head[u],v,w},head[u]=elen;
edge[++elen]=(Edg){head[v],u,w},head[v]=elen;
// cout< naive 的，我们猜想 \(k>2\) 是不是直接设一个超级源点，超级汇点就可以了
发现不是很刑，你这样割，把白点割到汇点所属集合里面怎么办
这样做还有一个问题是，因为我们是要先转化对偶图的（直接在原图上跑会 T 飞），而路径可能会交叉，那咋转对偶图
我们考虑把问题转化到 \(k=2\) 的情况。
首先，我们顺时针把射线连起来，同时，从某一个特殊点开始，如若 \(i+1\) 不是特殊点/颜色和 \(i\) 一样，那么我们认为 \(i,i+1\) 同属一个连通块，于是大致形成了这样的情况：
（图源：约瑟夫用脑玩）
容易发现红色数量必然和蓝色数量相同（奇数直接合并在一起）
给出一个结论：将一个红色块和一个蓝色块两两配对跑最短路，再去掉这些最短路对应的原图的边集，那么答案方案就是这些边集权值和
可以说明的是，不用担心路径重复的问题，因为如若重复，那么交换一下配对方式肯定可以干掉重复的路径而且显然更优。
结论的证明可以感性理解一下。最后的答案肯定是长成这个形式，因为我如若有一个割是从某个连通块内部出发的，那显然不是很有用；也不会是路径走到一半就断掉，走一半断掉没有起到分割颜色的作用，不如不走。
具体证明可以看：此处 大意是暴力分类讨论。
具体的，由于引入了新点（连通块代表点），可以将相邻连通块之间的权值设为第二个（顺时针）连通块的第一条射线权值（按照上面所述划分连通块方式，这必定是一个特殊射线）
对于连通块内的射线之间，边权 \(0\) 好了，以防止这样的情况：
（图源：Piwry，我怎么在到处嫖图 /fn
为了找到最优的配对方式，我们可以执行一个区间 DP 的过程
首先管都不管，跑 \(k\) 次最短路，预处理数组 \(dis[x][y]\) 表示第 \(x\) 个特殊点到第 \(y\) 个特殊点的最短路
然后设 \(dp[l][r]\) 表示匹配区间 \([l,r]\) 中的点的最小答案，注意这里破环为链
转移：\(dp[l][r]=min(dp[l+1][r-1]+dis[l][r],\min \{dp[l][k]+dp[k+1][r]\})\)
转移的时候特别注意一定时刻保证使用的 dp 值所代表的区间长度是偶数
所以总复杂度 \(O(\sum k (nm)\log (nm)+\sum k^3)\)
Code
代码学习自：Piwry
#include
#define id(i,j) ((i)*(m+1)+(j))
#define pii pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 5e2+5;
const int K = 55;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
int s=0,w=1; char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
bool cmin(ll&a,ll b){return a>b?a=b,1:0;}
bool cmin(int&a,int b){return a>b?a=b,1:0;}
struct Dijkstra{
struct Edge{int nex,to,dis;}edge[N*N*4];
priority_queue,greater >q;
int head[N*N],orihead[N*4*2],orid[N*4*2];
//双向边两倍，一共 4n 条射线，每条射线像所属连通块连边
int dis[N*N],vis[N*N];
int elen,orielen;
void addedge(int u,int v,int w){
edge[++elen]=(Edge){head[u],v,w},head[u]=elen;
edge[++elen]=(Edge){head[v],u,w},head[v]=elen;
// cout<vec;
int n,m,T,siz;
signed main(){
n=read(),m=read(),T=read(),siz=(n+1)*(m+1);
for(int i=1;i