题解 P4510 [CTSC2015]性别改造计划

· · 题解

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

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

我们观察目标式子：

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