HNOI2006 潘多拉的盒子

时间:2021-12-01 04:07:50

题目描述

题解:

题目的描述比较长,理解起来也有一定难度。仔细读题后我们发现整个任务可以分成两个部分:找出咒语机之间所有的升级关系、求最长升级序列。

1、 求升级关系:

容易看出,咒语机i可以抽象成一个图Gi,其顶点集Vi为ni个元件,每个顶点发出两条边——“0”边和“1”边,分别表示将信号加“0”和加“1”。

我们枚举两个咒语机A、B(A≠B),判断B是否是A的升级。最简单的想法是生成出A和B的所有咒语源,然后判断前者是否为后者的子集。但是,一个咒语机产生的咒语源可能有无限多个,无法逐一判断。

其实,只要存在一个咒语源,A能够产生而B不能产生,那么这一升级关系就不成立。为了找到(或者证明不存在)这样的一个咒语源,我们构造图H,其顶点是一个二元组(i,j),表示图GA的顶点i和图GB的顶点j。如果图GA的顶点i走“c”边到达顶点ic(c=0,1),图GB的顶点j走“c”边到达顶点jc,那么从图H的顶点(i,j)连有向边到(ic,jc)。我们将图H中的某些顶点(i,j)称为“关键顶点”,其特点是:图GA的顶点i是输出元而图GB的顶点j不是输出元。存在一个A能够产生而B不能的咒语源,等价于图H中存在从顶点(0,0)到关键顶点的路径。我们只需用广度优先搜索遍历图H即可。

2、 求最长升级序列:

假设第1部分求出的升级关系保存在图G中:如果咒语机B是A的升级,那么图G中从A向B连一条有向边。最长升级序列在图中对应最长路经。如果G是有向无环图,那么可以用拓扑排序加上动态规划的方法求最长路径。可惜的是,G有可能存在环,并且只有一种可能:存在若干个咒语机,它们产生的咒语源完全相同。显然,在这种情况下,只要选择其中一个,那么与之相同的所有咒语机都可以被选择。因此,我们把图中所有相同的咒语机合并成一个结点,并用num域记录该结点是由多少个结点合并而来(如图1)。

这样,问题转化为在一个有向无环图中求带权最长路经,这同样可以用拓扑排序加上动态规划的方法解决。具体的方法是:首先将图的顶点重新编号使得1,2,…,n是图的拓扑序,然后利用状态转移方程求解即可。

以上两个部分中,第一部分的时间复杂度为O(n2s2),第二部分的时间复杂度为O(s2),所以算法的总时间复杂度为O(n2s2)。

代码:

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ;
int s;
struct node
{
int n,m;
bool ot[N];
int ch[N][];
void read()
{
scanf("%d%d",&n,&m);
for(int a,i=;i<=m;i++)
{
scanf("%d",&a);
ot[a]=;
}
for(int i=;i<n;i++)
{
scanf("%d%d",&ch[i][],&ch[i][]);
}
}
}p[N];
int hed[N],cnt;
struct EG
{
int fr,to,nxt;
}e[N*N],e0[N*N];
void ae(int f,int t)
{
e[++cnt].fr = f;
e[cnt].to = t;
e[cnt].nxt = hed[f];
hed[f] = cnt;
}
struct Pair
{
int x,y;
Pair(){}
Pair(int x,int y):x(x),y(y){}
};
bool vs[N][N];
bool check(node &a,node &b)
{
memset(vs,,sizeof(vs));
queue<Pair>q;
q.push(Pair(a.ch[][],b.ch[][]));
q.push(Pair(a.ch[][],b.ch[][]));
while(!q.empty())
{
Pair u = q.front();
q.pop();
if(!a.ot[u.x]&&b.ot[u.y])return ;
if(vs[u.x][u.y])continue;
vs[u.x][u.y]=;
q.push(Pair(a.ch[u.x][],b.ch[u.y][]));
q.push(Pair(a.ch[u.x][],b.ch[u.y][]));
}
return ;
}
int dep[N],low[N],tot;
bool vis[N];
int bel[N],bc,siz[N],sta[N],tl;
void tarjan(int u)
{
dep[u]=low[u]=++tot;
vis[u]=;
sta[++tl] = u;
for(int j=hed[u];j;j=e[j].nxt)
{
int to = e[j].to;
if(!dep[to])
{
tarjan(to);
low[u] = min(low[u],low[to]);
}else if(vis[to])
{
low[u] = min(low[u],dep[to]);
}
}
if(dep[u]==low[u])
{
bc++;
int c = -;
while(c!=u)
{
c = sta[tl--];
bel[c]=bc;
siz[bc]++;
vis[c] =;
}
}
}
bool eg[N][N];
int Hed[N],Cnt;
void AE(int f,int t)
{
e0[++Cnt].to = t;
e0[Cnt].nxt = Hed[f];
Hed[f] = Cnt;
}
int dp[N];
int dfs(int u)
{
if(dp[u])return dp[u];
if(!Hed[u])return dp[u]=siz[u];
for(int j=Hed[u];j;j=e0[j].nxt)
dp[u]=max(dp[u],dfs(e0[j].to)+siz[u]);
return dp[u];
}
int main()
{
// freopen("pandora.in","r",stdin);
// freopen("pandora.out","w",stdout);
scanf("%d",&s);
for(int i=;i<=s;i++)p[i].read();
for(int i=;i<=s;i++)
for(int j=;j<=s;j++)
if(i!=j&&check(p[i],p[j]))
ae(i,j);
for(int i=;i<=s;i++)
if(!dep[i])tarjan(i);
for(int j=;j<=cnt;j++)
{
int f = bel[e[j].fr],t = bel[e[j].to];
if(f!=t&&!eg[f][t])eg[f][t]=,AE(f,t);
}
int ans = ;
for(int i=;i<=bc;i++)ans=max(ans,dfs(i));
printf("%d\n",ans);
return ;
}