自动搬运

查看原文

来自洛谷，原作者为

	RPChe_ Ends, then begins.

搬运于2025-08-24 22:00:52，当前版本为作者最后更新于2021-08-28 14:44:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

既然这题没有题解那我就来一发吧（

首先因为题面过于复杂这里就不提供题意简述了，如果还没有完全了解题意建议再多读几遍题。

我们观察目标式子：

$$\text{Profit} = \lfloor10\ln(1+A)\rfloor \times S-C $$

注意到改造后血缘链相邻两者为异性的情况数量 $A$ 的上界是 $N\times K=200$ ，即 $\lfloor10\ln(1+A)\rfloor \in [0,52]$ ，并不大，那么我们考虑枚举这部分的值，算完以后再检验。

我们称辈分关系为深度，羊为点，那么显然深度不同的点之间不会相互影响。于是我们考虑设计一个DP，令 $f_{i,j,s}$ 表示当前做到第 $i$ 层，血缘链相邻两点为异性的情况数量为 $j$ ，所有血缘链上当前层的变性情况为 $s$ 时的最大收益。容易得出转移方程：

$$f_{i,j,s}=\max f_{i-1,j',s'}+P_{i,s}$$

其中 $P_{i,s}$ 表示当前层状态为 $s$ 时这一层点的最大收益。我们只需要枚举 $j'$，$s'$ 和 $s$ 就可以很方便的转移。

那么现在考虑如何计算 $P_{i,s}$。我们剥离出当前层的限制条件，发现其和这道题非常相似。于是我们可以使用同样的方式建立最小割模型来跑网络流，具体做法这里不再赘述。

做完DP以后我们需要再统一处理和血缘链没有关系的散点，然后对于某一个特定的 $\lfloor10\ln(1+A)\rfloor$ 值，我们在 $f_{n,j,s}$ 中枚举合法的 $j$ 和 $s$ 来统计答案就可以了。

算一下时间复杂度，$O(10\ln(NK)N2^K(O(\text{dinic})+NK2^K))$，不太过得去的样子。但是它显然是跑不满的，何况 $\text{dinic}$ 更跑不满，所以实际上它很轻松就跑过去了。

代码实现时需要注意细节，比如题目中的下取整。

#include<bits/stdc++.h>
#define rep(i,a,b) for(R int i=a;i<=b;i++)
#define R register
#define endl putchar('\n')
const int N=500005,inf=0x3f3f3f3f;
using namespace std;

int n,k,m,p,a[N],c[N],cn[5][55],x[N],y[N],b[N];
double d[N];
int f[55][205][16],ans,dep[N],fa[N],rv[N],sx[2][5];
int s,t,head[N],cnt,now[N],dis[N],flow;
struct edge { int a,b,next,f; } e[N];
queue<int> q;
char str[N];
int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
void add_edge(int a,int b,int f) {
	e[cnt]=(edge){a,b,head[a],f};
	head[a]=cnt++;
}
void add(int a,int b,int f) { add_edge(a,b,f),add_edge(b,a,0); }

bool bfs() {
	while(!q.empty()) q.pop();
	rep(i,1,t) dis[i]=now[i]=0;
	dis[s]=1,now[s]=head[s],q.push(s);
	while(!q.empty()) {
		int x=q.front(); q.pop();
		if(x==t) return 1;
		for(R int i=head[x];i!=-1;i=e[i].next) {
			if(e[i].f&&!dis[e[i].b]) {
				dis[e[i].b]=dis[x]+1;
				now[e[i].b]=head[e[i].b];
				q.push(e[i].b);
			}
		}
	}
	return 0;
}
int dfs(int x,int mn) {
	if(x==t) return mn;
	int res=0;
	for(R int i=now[x];i!=-1&&mn;i=e[i].next) {
		now[x]=i;
		if(e[i].f&&dis[e[i].b]==dis[x]+1) {
			int k=dfs(e[i].b,min(mn,e[i].f));
			if(!k) dis[e[i].b]=0;
			e[i].f-=k,e[i^1].f+=k;
			res+=k,mn-=k;
		}
	}
	return res;
}
void dinic() { while(bfs()) flow+=dfs(s,inf); }

void clear() {
	s=m+p*2+1,t=s+1,cnt=flow=0;
	rep(i,1,t) head[i]=-1,rv[i]=0;
}
int calc(int nw,int S,int ln) {
	clear();
	rep(i,1,k) rv[cn[i][nw]]=i;
	rep(i,1,m) {
		if(dep[i]==nw) {
			if(rv[i]) {
				if(S>>(rv[i]-1)&1) add(s,i,c[i]),add(i,t,inf);
				else add(s,i,inf);
			} else add(s,i,c[i]);
		}
	}
	int tot=0;
	rep(i,1,p) {
		if(dep[x[i]]==nw) {
			tot+=(b[i]+(int)(b[i]*d[i]))*ln;
			add(s,i+m,b[i]*ln),add(i+m,x[i],inf),add(i+m,y[i],inf);
			add(x[i],i+p+m,inf),add(y[i],i+p+m,inf),add(i+p+m,t,(int)(b[i]*d[i])*ln);
		}
	}
	dinic();
	return tot-flow;
}
int finish(int ln) {
	clear();
	rep(i,1,m) if(!dep[i]) add(s,i,c[i]),add(i,t,0);
	int tot=0;
	rep(i,1,p) {
		if(!dep[x[i]]) {
			tot+=(b[i]+(int)(b[i]*d[i]))*ln;
			add(s,i+m,b[i]*ln),add(i+m,x[i],inf),add(i+m,y[i],inf);
			add(x[i],i+p+m,inf),add(y[i],i+p+m,inf),add(i+p+m,t,(int)(b[i]*d[i])*ln);
		}
	}
	dinic();
	return tot-flow;
}
int solve(int ln) {
	int lim=(1<<k)-1;
	memset(f,-inf,sizeof f);
	rep(s,0,lim) f[1][0][s]=calc(1,s,ln);
	rep(i,2,n) {
		rep(s,0,lim) {
			int res=calc(i,s,ln);
			rep(j,0,k-1) sx[0][j]=a[cn[j][i]]^((s>>j)&1);
			rep(sp,0,lim) {
				rep(j,0,k-1) sx[1][j]=a[cn[j][i-1]]^((sp>>j)&1);
				rep(j,0,n*k) {
					int nw=j;
					rep(l,0,k-1) nw+=sx[0][l]^sx[1][l];
					f[i][nw][s]=max(f[i][nw][s],f[i-1][j][sp]+res);
				}
			}
		}
	}
	int res=0;
	rep(i,0,n*k) {
		if(floor(10.0*log(1+i))==ln) {
			rep(s,0,lim) res=max(res,f[n][i][s]);
		}
	}
	return res+finish(ln);
}

void init() {
	rep(i,1,m) {
		a[i]=str[i]=='M';
		dep[i]=dep[find(i)];
	}
}

int main() {
	scanf("%d%d%d%d%s",&n,&k,&m,&p,str+1);
	rep(i,1,m) fa[i]=i;
	rep(i,1,m) scanf("%d",&c[i]);
	rep(i,1,k) rep(j,1,n) {
		scanf("%d",&cn[i][j]);
		dep[cn[i][j]]=j;
	}
	rep(i,1,p) {
		scanf("%d%d%d%lf",&x[i],&y[i],&b[i],&d[i]);
		int fx=find(x[i]),fy=find(y[i]);
		if(dep[fx]) fa[fy]=fx;
		else fa[fx]=fy;
	}
	init();
	rep(ln,0,53) ans=max(ans,solve(ln));
	printf("%d\n",ans);
	return 0;
}