ABC354G 题解

· · 题解

怎么 abc 还出网络流。

题意简述

给你 n 个字符串 s_i，每个字符串有权值 a_i，你需要从中选出一些字符串，选出字符串的下标组成一个集合 S。

你需要满足对于任意的 i\in S，不存在 j\in S(i\neq j) 使得 s_i 是 s_j 的子串。

任务是最大化 \sum_{i\in S}a_i。

数据范围：n\leq 100,\sum |s_i|\leq 5000。

解法

看到奇怪的数据范围没有什么头猪，不妨往一些玄学复杂度的东西上想，如网络流。

建立一个图。对于每个 s_i,s_j(i<j)，若 s_i 是 s_j 的子串，则在图上从 i 到 j 连一条有向边，容易知道这是一个 DAG。

现在我们把这个问题转化成了形式化问题：

给定一个 DAG，每个点有点权，你需要在 DAG 中选定一些点，使得没有任意两个点在一条链上，最大化权值和。

这个问题可以直接使用网络流解决。

具体地，把每个点 i 拆成左部点 L(i) 和右部点 R(u)，然后从 S 向 L(i) 连容量为 a_i 的边，从 R(i) 到 T 连容量为 a_i 的边。

对于原图中每条边 (u,v)，从 L(u) 到 R(v) 连容量为 \inf 的边。

让 \sum_{i=1}^n a_i 减去最大流就是答案。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
namespace mf{
    const int N=1e5+10,M=1e5+10;
    int s,t;
    struct edge{
        int v,nxt;
        ll w;
    }e[M*2];
    int head[N],cnt=2;
    void add(int u,int v,ll w){
        e[cnt].v=v;
        e[cnt].w=w;
        e[cnt].nxt=head[u];
        head[u]=cnt++;
    }
    void addflow(int u,int v,ll w){
        add(u,v,w);
        add(v,u,0);
    }
    int d[N],cur[N];
    bool bfs(){
        memset(d,0,sizeof(d));
        queue<int> q;
        q.push(s);
        d[s]=1,cur[s]=head[s];
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt){
                if(!d[e[i].v]&&e[i].w){
                    d[e[i].v]=d[u]+1;
                    cur[e[i].v]=head[e[i].v];
                    if(e[i].v==t)return 1;
                    q.push(e[i].v);
                }
            }
        }
        return 0;
    }
    ll dinic(int u,ll flow){
        if(u==t)return flow;
        ll rm=flow;
        for(int i=cur[u];i&&rm;i=e[i].nxt){
            cur[u]=i;
            if(e[i].w&&d[e[i].v]==d[u]+1){
                ll k=dinic(e[i].v,min(e[i].w,rm));
                if(!k)d[e[i].v]=0;
                rm-=k;
                e[i].w-=k;
                e[i^1].w+=k;
            }
        }
        return flow-rm;
    }
    ll Maxflow(){
        ll ans=0;
        while(bfs())ans+=dinic(s,INFL);
        return ans;
    }
}
const int N=110;
ll n,a[N],sum;
string s[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    mf::s=0,mf::t=n*2+1;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    for(int i=1;i<=n;i++){
        mf::addflow(mf::s,i,a[i]);
        mf::addflow(i+n,mf::t,a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            if(s[i]==s[j]&&i<j)continue;
            if(s[i].find(s[j])!=string::npos){
                mf::addflow(i,j+n,INFL);
            }
        }
    }
    cout<<sum-mf::Maxflow()<<endl;
    return 0;
}