题目描述
懒得写了。。。直接贴题面
$\sum n\leq5000,1\leq S_{i,j}\leq k\leq 1000 $
题解
先建出广义sam。
可以发现朋友的出现位置的定义符合后缀自动机的right集合的定义，如果一群人会相互产生感情，那么这一群人的特征值序列一定是sam中的同一个点（right集合相同）。
然后发现题目求的就是用最少的“从根开始，在根之外的点不想交的路径”覆盖整个sam。
这是一个经典问题，可以用网络流解决。
把除了根之外每个点拆成两个点，两个点之间连上下界都是\(1\)的边。sam中的转移连下界为\(0\)上界为\(1\)边。所有点都往汇点连下界为\(0\)上界为\(1\)的边。
上下界最小流就是答案。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<iostream>
#include<tr1/unordered_map>
#include<queue>
using namespace std;
using namespace tr1;
typedef long long ll;
typedef pair<int,int> pii;
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[100];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
sprintf(str,"%s.out",s);
freopen(str,"w",stdout);
#endif
}
namespace flow
{
int u[1000010];
int v[1000010];
int h[100010];
int t[1000010];
int c[1000010];
int cnt;
void add2(int a,int b,int d)
{
cnt++;
u[cnt]=a;
v[cnt]=b;
c[cnt]=d;
t[cnt]=h[a];
h[a]=cnt;
}
void add(int x,int y,int v)
{
add2(x,y,v);
add2(y,x,0);
}
int S,T;
void add(int x,int y,int u,int v)
{
add(x,T,u);
add(S,y,u);
add(x,y,v-u);
}
int num;
int e[1000010];
int d[1000010];
int cur[100010];
queue<int> q;
int op(int x)
{
return ((x-1)^1)+1;
}
void init()
{
memset(d,-1,sizeof d);
d[T]=0;
q.push(T);
while(!q.empty())
{
int x=q.front();
q.pop();
e[d[x]]++;
for(int i=h[x];i;i=t[i])
if(c[op(i)]&&d[v[i]]==-1)
{
d[v[i]]=d[x]+1;
q.push(v[i]);
}
}
}
int dfs(int x,int flow)
{
if(x==T)
return flow;
int s=0,u;
for(int &i=cur[x];i;i=t[i])
if(c[i]&&d[v[i]]==d[x]-1)
{
u=dfs(v[i],min(c[i],flow));
flow-=u;
s+=u;
c[i]-=u;
c[op(i)]+=u;
if(!flow)
return s;
}
e[d[x]]--;
if(!e[d[x]])
d[S]=num;
d[x]++;
e[d[x]]++;
cur[x]=h[x];
return s;
}
int solve()
{
int ans=0;
init();
memcpy(cur,h,sizeof h);
while(d[S]>=0&&d[S]<=num-1)
ans+=dfs(S,0x3fffffff);
return ans;
}
}
namespace sam
{
unordered_map<int,int> next[10010];
int fail[10010];
int len[10010];
int n;
void init()
{
n=1;
}
int insert(int p,int c)
{
if(next[p][c])
{
int np=next[p][c];
if(len[np]==len[p]+1)
return np;
int nq=++n;
len[nq]=len[p]+1;
next[nq]=next[np];
fail[nq]=fail[np];
fail[np]=nq;
for(;p&&next[p][c]==np;p=fail[p])
next[p][c]=nq;
return nq;
}
int np=++n;
len[np]=len[p]+1;
for(;p&&!next[p][c];p=fail[p])
next[p][c]=np;
if(!p)
fail[np]=1;
else
{
int q=next[p][c];
if(len[q]==len[p]+1)
fail[np]=q;
else
{
int nq=++n;
len[nq]=len[p]+1;
next[nq]=next[q];
fail[nq]=fail[q];
fail[q]=fail[np]=nq;
for(;p&&next[p][c]==q;p=fail[p])
next[p][c]=nq;
}
}
return np;
}
}
int main()
{
open("friend");
int k,m,now,n,x;
scanf("%d%d",&k,&m);
sam::init();
while(m--)
{
now=1;
scanf("%d",&n);
while(n--)
{
scanf("%d",&x);
now=sam::insert(now,x);
}
}
flow::S=2*sam::n+1;
flow::T=2*sam::n+2;
flow::num=2*sam::n+2;
for(int i=2;i<=sam::n;i++)
{
flow::add(i*2-2,i*2-1,1,1);
flow::add(i*2-1,2*sam::n,0,1);
}
for(int i=1;i<=sam::n;i++)
for(auto v:sam::next[i])
flow::add(2*i-1,2*v.second-2,0,1);
flow::solve();
flow::add(2*sam::n,1,0,0x3fffffff);
int ans=flow::solve();
for(int i=1;i<=flow::cnt;i+=6)
{
if(flow::c[i])
{
printf("0\n");
return 0;
}
if(flow::c[i+2])
{
printf("0\n");
return 0;
}
}
printf("%d\n",ans);
return 0;
}