题目分析
题意
给定 \(n\) 个字符串,要求从中选出若干个组成一个集合,且集合中每个字符串都互不包含。
求集合中字符串的权值的和的最大值。
分析
首先很容易想到用 KMP 判两个串是否存在包含关系。
考虑建图,将不能同时存在于一个集合中的串的节点相连。
然后发现只需求出这个图的最大权独立集就行了。
但是我不会。
因为字符串间的包含关系是一种非严格偏序关系。
所以说如果保证给定字符串 \(S_i\) 互不相同,那么建出来的图就是 DAG。
在这个图上跑最大权反链即可。
但是字符串可能相同,如果没有考虑这种情况会 WA 1 个点。
可以直接把两个相同的串之间的边断掉一条,成功 AC。
Code
#include<bits/stdc++.h>
using namespace std;
template<typename Tp, size_t sizn, size_t sizm>
struct netflow
{
int cnt=1, s=sizn-2, t=sizn-3;
Tp val[sizm<<1], dis[sizn];
void link(int u, int v, Tp w)
{
// println(cerr, "{} {} {}", u, v, w);
to[++cnt]=v; val[cnt]=w;
nxt[cnt]=head[u]; head[u]=cnt;
to[++cnt]=u; val[cnt]=0;
nxt[cnt]=head[v]; head[v]=cnt;
}
int head[sizn], to[sizm<<1], nxt[sizm<<1], now[sizm<<1];
Tp inf=numeric_limits<Tp>::max()/2;
int bfs()
{
for(int i=1;i<sizn;i++) dis[i]=inf;
dis[t]=inf;
queue<int> q;
q.push(s);
dis[s]=0;
now[s]=head[s];
while(!q.empty())
{
int idx=q.front(); q.pop();
for(int i=head[idx];i;i=nxt[i])
{
int arr=to[i];
if(val[i]>0&&dis[arr]==inf)
{
q.push(arr);
now[arr]=head[arr];
dis[arr]=dis[idx]+1;
if(arr==t) return 1;
}
}
}
return 0;
}
Tp dfs(int idx, Tp sum)
{
if(idx==t) return sum;
Tp k, res=0;
for(int i=now[idx];i&∑i=nxt[i])
{
now[idx]=i;
int arr=to[i];
if(val[i]>0&&(dis[arr]==dis[idx]+1))
{
k=dfs(arr, min(sum, val[i]));
if(k==0) dis[arr]=inf;
val[i]-=k; res+=k;
val[i^1]+=k; sum-=k;
}
}
return res;
}
Tp maxflow()
{
Tp ans=0;
while(bfs()) ans+=dfs(s, inf);
return ans;
}
};
netflow<int64_t, 10005, 100005> nf;
#define maxn 5003
#define l(x) ((x)<<1)
#define r(x) ((x)<<1|1)
namespace KMP
{
int nxt[maxn];
void build(const string &k)
{
memset(nxt, -1, sizeof nxt);
for(int i=1,j=-1;i<k.size();i++)
{
while(~j&&k[j+1]!=k[i]) j=nxt[j];
if(k[i]==k[j+1]) j++;
nxt[i]=j;
}
}
bool chk(const string &k, const string &t)
{
for(int i=0, j=-1;i<t.size();i++)
{
while(~j&&k[j+1]!=t[i]) j=nxt[j];
if(k[j+1]==t[i]) j++;
if(j==k.size()-1) return 1;
}
return 0;
}
}
string ss[102];
bitset<102> bs[102];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>ss[i];
for(int i=1;i<=n;i++)
{
KMP::build(ss[i]);
for(int j=1;j<=n;j++)
{
if(i==j) continue;
if(KMP::chk(ss[i], ss[j]))
bs[i][j]=1;
}
}
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
if(bs[i][j]&&bs[j][i])
bs[i][j]=0;
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
if(bs[i][j])
bs[i]|=bs[j];
for(int j=1;j<=n;j++)
for(int i=1;i<=n;i++)
if(bs[i][j]) nf.link(l(i), r(j), nf.inf);
int64_t sum=0;
for(int64_t i=1, w;i<=n;i++)
{
cin>>w;
nf.link(nf.s, l(i), w);
nf.link(r(i), nf.t, w);
sum+=w;
}
int64_t ret=nf.maxflow();
cout<<(sum-ret)<<'\n';
}
标签:arr,val,idx,int,题解,sum,ABC354G,Select,dis
From: https://www.cnblogs.com/redacted-area/p/18379550