题解 P2321 【[HNOI2006]潘多拉的宝盒】

本文主要是介绍题解 P2321 【[HNOI2006]潘多拉的宝盒】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

做这道题的最关键的一步也是第一步：读懂题！！！！！！！

题目大意：

有s个咒语机，每个咒语机出度为2，字符串后加0指向一个元件，加1指向一个元件，直到找到一个输出元，算是一种方案；当A咒语机的所有方案包含B咒语机的所有方案时，那么A咒语机是B咒语机的升级。求：最长升级序列的长度。（我读了40分钟才读懂，语文不好）

做法：

我一开始是没有思路的，感觉像搜索，看了网上很多代码都是Tarjan+DFS+……（本人很懒，不想学这种方法），最后找到一个dalao的code，我把他的思路介绍给大家：

1.pri[i][x]记录的是输出元；

2.vis[i][j]记录的是s1中的i元件和s2中的j元件这个状态；

3.map[i][j][（0,1）]记录的是i咒语机中j元件到哪个元件；（因为n很小，所以开矩阵就好）

4.一个BFS来判断j是否是i的升级，用levup[i][j]记录；

5.Floyd找出最长升级序列。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=55;
int map[N][N][2],n,m,levup[N][N],ans=0;
bool vis[N][N],pri[N][N];
struct node
{int sx,sy;
};
bool check(int s1,int s2)//判断s2是否是s1的升级 
{memset(vis,0,sizeof(vis));queue<node>q;node fir;fir.sx=0,fir.sy=0;q.push(fir);while(!q.empty()){node x=q.front(),tmp;q.pop();if(pri[s1][x.sx]&&!pri[s2][x.sy])return 0;//如果 pri[s1][x.sx]是输出元，且pri[s2][x.sy]不是的话，那么s2不是s1的升级 tmp.sx=map[s1][x.sx][0],tmp.sy=map[s2][x.sy][0];if(!vis[tmp.sx][tmp.sy])vis[tmp.sx][tmp.sy]=true,q.push(tmp);tmp.sx=map[s1][x.sx][1],tmp.sy=map[s2][x.sy][1];if(!vis[tmp.sx][tmp.sy])vis[tmp.sx][tmp.sy]=true,q.push(tmp);}return 1;
}
int main()
{int s;scanf("%d",&s);for(int i=0;i<s;i++)//因为是从0号元件开始的所以i=0;i<s;i++ {scanf("%d%d",&n,&m);for(int j=0;j<m;j++){int x;scanf("%d",&x);pri[i][x]=1;}for(int j=0;j<n;j++){int u,v;scanf("%d%d",&u,&v);map[i][j][0]=u,map[i][j][1]=v;}}memset(levup,-0x3f,sizeof(levup));for(int i=0;i<s;i++){for(int j=0;j<s;j++){if(check(i,j)&&i!=j&&levup[j][i]<0)//这里是levup[j][i]!!!!!!!!!!!  j  !!!!!!  i  !!!!!!!!//因为要i不是j的升级，避免重复，否者ans很大，最开始我写的levup[i][j]全WA levup[i][j]=1;//这里是levup[i][j]!!!!!!!!!!!  i  !!!!!!  j  !!!!!!!! }}for(int k=0;k<s;k++)//floyd(一个精巧的DP) {for(int i=0;i<s;i++){for(int j=0;j<s;j++){if(levup[i][j]<levup[i][k]+levup[k][j]&&levup[i][k]&&levup[k][j])levup[i][j]=levup[i][k]+levup[k][j],ans=max(ans,levup[i][j]);}}}printf("%d",ans+1);//因为要把开头的咒语机算进去，所以ans+1 
}
欢迎dalao指正！！！！！！！！！！