Problem Link

题目大意

构造 $x_1\sim x_n$，满足 $x_i\in [l_i,r_i]\subseteq[1,k]$ 以及 $m$ 条限制形如 $|x_u-x_v|\le w$。

$q$ 次询问给定 $v_1\sim v_k$，其中 $v_1=v_k=0$，最大化 $10^6\sum_{i,j}[|x_i-x_j|\le 1]+\sum v_i\sum_j [x_j=i]$。

数据范围：$n\le 600,m\le 3n,q\le 3\times 10^5,k\le 5$。

思路分析

只分析 $k=5$ 的情况。

首先显然填 $1,5$ 的元素越少越好，可以预处理出这样的元素。

剩余的元素在 $2,3,4$ 中选择，则答案为 $\sum v_ic_i+10^6(n^2-2(c_2c_4-c_1c_4-c_2c_5-c_1c_5-c_3c_1-c_3c_5))$。

那么答案可以看成一个有关 $x=c_2,y=c_4$ 的函数 $f(x,y)=axy+bx+cy+d$，其中 $a=-2\times 10^6$。

转写成求 $\max a(x-x_0)(y-y_0)$，即最小化 $(x-x_0)(y-y_0)$。

把所有的 $(x,y)$ 画在平面上，设他们占据的范围为 $[x_L,x_R]\times [y_L,y_R]$，由于这些限制可以把一些填 $2,4$ 的点直接调成 $3$，因此一定能取到 $(x_L,y_L),(x_R,y_L)(x_L,y_R)$。

如果这个矩形平移 $(-x_0,-y_0)$ 后经过二四象限，则答案一定在 $(x_L,y_R)$ 或 $(x_R,y_L)$ 上取到。

否则要么全在第一象限要么全在第三象限，第一种情况答案在 $(x_L,y_L)$ 上取到。

否则相当于求 $(x,y)$ 的上凸壳，类似 最小乘积生成树，分治构造凸包，每次求出距离当前区间左右端点最远的点，这个点一定在凸包上。

而这个问题相当于求一组解最大化 $z_2c_2+z_4c_4$，先转成最小化 $z_4c_2+(z_2+z_4)c_3+z_2c_4$。

然后把 $w=0$ 的限制对应连通块缩起来，限制是有些点不能一个填 $2$ 一个填 $4$，这是经典的切糕模型，网络流解决。

可以证明凸壳上点数不会超过 $\mathcal O(n^{2/3})$ 级别。

时间复杂度 $\mathcal O(n^{2/3}(q+\mathrm{Flow}(n,m)))$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=605,Z=1e6,inf=1e9;
int k,n,m,q,L[MAXN],R[MAXN],c[6];
int dsu[MAXN],bl[MAXN],id[MAXN],sz[MAXN],tot;
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
vector <array<int,2>> vc,lim;
struct Flow {
static const int MAXV=1205,MAXE=2e5+5;
struct Edge {
	int v,f,lst;
}	G[MAXE];
int S,T,ec=1,vc,hd[MAXV],cur[MAXV],dep[MAXV];
void init() { ec=1,memset(hd,0,(vc+1)<<2); }
void adde(int u,int v,int w) { G[++ec]={v,w,hd[u]},hd[u]=ec; }
void link(int u,int v,int w) { adde(u,v,w),adde(v,u,0); }
bool BFS() {
	memcpy(cur,hd,(vc+1)<<2),memset(dep,-1,(vc+1)<<2);
	queue <int> Q;
	Q.push(S),dep[S]=0;
	while(!Q.empty()) {
		int u=Q.front(); Q.pop();
		for(int i=hd[u];i;i=G[i].lst) if(G[i].f&&dep[G[i].v]==-1) {
			dep[G[i].v]=dep[u]+1,Q.push(G[i].v);
		}
	}
	return ~dep[T];
}
int dfs(int u,int f) {
	if(u==T) return f;
	int r=f;
	for(int i=cur[u];i;i=G[i].lst) {
		int v=G[cur[u]=i].v;
		if(G[i].f&&dep[v]==dep[u]+1) {
			int g=dfs(v,min(r,G[i].f));
			if(!g) dep[v]=-1;
			G[i].f-=g,G[i^1].f+=g,r-=g;
		}
		if(!r) return f;
	}
	return f-r;
}
int Dinic() {
	int f=0;
	while(BFS()) f+=dfs(S,inf);
	return f;
}
}	F;
void build(array<int,2>a,array<int,2>b) {
	int wx=a[1]-b[1],wy=b[0]-a[0];
	int s=F.S=2*tot+1,t=F.T=F.vc=2*tot+2;
	F.init();
	for(int i=1;i<=tot;++i) {
		F.link(s,i,L[id[i]]==2?sz[i]*wy:inf);
		F.link(i,i+tot,sz[i]*(wy+wx));
		F.link(i+tot,t,R[id[i]]==4?sz[i]*wx:inf);
	}
	for(auto e:lim) F.link(e[0]+tot,e[1],inf),F.link(e[1]+tot,e[0],inf);
	F.Dinic();
	array<int,2>o{c[2],c[4]};
	for(int i=1;i<=tot;++i) {
		if(F.dep[i]==-1) o[0]+=sz[i];
		if(~F.dep[i+tot]) o[1]+=sz[i];
	}
	if(o[0]*wx+o[1]*wy>a[0]*wx+a[1]*wy) vc.push_back(o),build(a,o),build(o,b);
}
void solve() {
	cin>>k>>n>>m>>q;
	for(int i=1;i<=n;++i) cin>>L[i]>>R[i];
	vector <array<int,3>> edg;
	for(int i=1,u,v,w;i<=m;++i) {
		cin>>u>>v>>w,edg.push_back({u,v,w});
	}
	for(int t=1;t<=n;++t) for(auto e:edg) {
		int u=e[0],v=e[1],w=e[2];
		L[v]=max(L[v],L[u]-w),R[v]=min(R[v],R[u]+w);
		L[u]=max(L[u],L[v]-w),R[u]=min(R[u],R[v]+w);
	}
	for(int i=1;i<=n;++i) {
		if(R[i]>1&&L[i]<k) L[i]=max(L[i],2),R[i]=min(R[i],k-1);
		if(L[i]==R[i]) ++c[L[i]];
	}
	if(k==3) vc={{n-c[1]-c[3],n-c[1]-c[3]}};
	else if(k==4) vc={{c[2],n-c[1]-c[2]-c[4]},{n-c[1]-c[3]-c[4],c[3]}};
	else {
		int m2=0,m4=0;
		for(int i=1;i<=n;++i) m2+=L[i]==2,m4+=R[i]==4;
		vc={{c[2],c[4]},{c[2],m4},{m2,c[4]}};
		tot=0,lim.clear(),iota(dsu+1,dsu+n+1,1);
		for(auto e:edg) if(!e[2]) dsu[find(e[0])]=find(e[1]);
		for(int i=1;i<=n;++i) if(L[i]!=R[i]&&dsu[i]==i) id[++tot]=i,bl[i]=tot;
		for(int i=1;i<=n;++i) if(L[i]!=R[i]) ++sz[bl[find(i)]];
		for(auto e:edg) if(e[2]==1) {
			int x=bl[find(e[0])],y=bl[find(e[1])];
			if(x&&y) lim.push_back({x,y});
		}
		build(vc[1],vc[2]);
	}
	while(q--) {
		array <ll,6> vt={0,0,0,0,0,0};
		for(int i=2;i<k;++i) cin>>vt[i];
		ll ans=0;
		for(auto o:vc) {
			auto e=c;
			e[2]=o[0],e[k-1]=o[1];
			if(k==5) e[3]=n-e[1]-e[2]-e[4]-e[5];
			ll s=0;
			for(int i=1;i<=k;++i) s+=vt[i]*e[i]+1ll*(e[i]+2*e[i-1])*e[i]*Z;
			ans=max(ans,s);
		}
		cout<<ans<<"\n";
	}
	memset(sz,0,sizeof(sz)),memset(c,0,sizeof(c)),memset(bl,0,sizeof(bl)),tot=0;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int ty,_; cin>>ty>>_;
	while(_--) solve();
	return 0;
}