暂时没写关于拓补排序和不下降序列的专题…先把这道码量巨大的题写出来，免得忘了…
Description
xxxxxyt学姐经常一个人在家，难免会感到寂寞，于是学姐养了n只可爱的宠物，比如皮皮虾、大蟒蛇、藏狐、安康鱼…但即便如此学姐还是感到无聊。突然有一天，学姐想到
了让宠物们互相对战的消遣方法（请不要给动物保护协会打电话！）。学姐让宠物们两两进
行对战，n*(n-1)/2场对战后，学姐得到了一张相生相克图，然后又根据自己的喜好，把
宠物们分成了一队与二队。就在队伍分好后，学姐的强迫症又犯了，她希望自己的两支队伍
都满足这样一个性质：存在某种排列，使得排在后面的宠物能够击败排在前面的所有宠物。
但学姐的懒惰大家都是知道的，所以她找到了你，希望你能告诉她这两支队伍是否均满足要
求，如果是，她还希望你告诉她最多可以从二队中抽出多少只宠物放在一队，使得两支队伍
仍然满足要求。努力解决问题吧，而xxxxxyt学姐，瘫躺。
Input
第一行输入两个数字n和m，分别表示学姐有n只宠物，其中被分到一队的宠物有m
只。
接下来n行每行n个数字，ai,j
表示第i只宠物是否能战胜第j只宠物，保证ai,i=0
且ai,j=!aj,i
。
接下来一行m个数字，表示有哪些宠物被分到了一队。
Output
如果两支队伍均不能让xxxxxyt满意，则输出“NO”；否则输出“YES”，并输出一个
最大的k，使得从二队中非任意地抽出k只宠物放入一队后，两支队伍仍然满足条件。详细
格式见样例输出。
Sample Input 1
3 2
0 1 1
0 0 1
0 0 0
3 1
Sample Output 1
YES 1
Sample Input 2
4 3
0 1 0 1
0 0 1 1
1 0 0 1
0 0 0 0
1 2 3
Sample Output 2
NO
Sample Input 3
4 2
0 1 0 1
0 0 1 1
1 0 0 1
0 0 0 0
1 2
Sample Output 3
YES 1
Hint
注意：
宠物们的实力是相对的，也就是可能会出现A战胜B，B战胜C，C又战胜A的
情况。
数据范围：
20%的数据1<=m<n<=10
60%的数据1<=m<n<=100
100%的数据1<=m<n<=100
Solution
首先要明白，如果想要一个明确的排列顺序，不可能存在 A>B B>C C>A的，这不是一个合法的线性排列。
那么，把战胜关系转换成有向图，这种不合法的排列就是一个环的形状。
如何判环，并且如果没有环的情况下能得出一个合法的排列？
这样就不难想到用拓补排序来解决了。（然而考试的时候并没想到，用深搜判环…炸的一塌糊涂…）
因为要分成两组队列，那么就需要把这张图根据队列成员来分开。
通过bool数组实现A序列和B序列的区分，分别单独统计在自己成员内的入度，然后进行拓补排序。
因为拓补排序的删边操作会破坏原图，所以在拓补前先备份一张原图。
如果存在有节点无法拓补排序，即存在环，那么输出NO结束程序。
否则进入第二个问题。
假定A序列长度为m。我们需要知道，序列B的成员i能插入序列A的第j位置，需要满足如下条件：
Aj+1、Aj+2…Am<Bi<A1、A2、A3…Aj（这里<符号的意义是能够战胜）
并且，Bi在Ai的插入位置j必须保持不下降，即不能破坏B的原序列顺序。
那么，这题就又转换到了最长不下降子序列长度问题了。求出每个Bi的插入位置，然后将所得的序列求最长不下降子序列。这样即保证了插入数量最多，又保证了序列没有和B序列冲突。
个人认为，最长序列写法要比那个动规好理解点…
下面是巨长的代码…
#include<iostream> #include<cstring> #include<queue> #include<cstdio> using namespace std; const int MAXSIZE = 1 << 22; const int MAXN=1002; inline char gc() {static char In[MAXSIZE], *at = In, *en = In;if (at == en){en = (at = In) + fread(In, 1, MAXSIZE, stdin);}return at == en ? EOF : *at++; } inline long long Read() {char c;while (c = gc(), !(c >= '0'&&c <= '9') && c != '-') {}bool f = c == '-';long long x = f ? 0 : c - '0';for (c = gc(); c >= '0'&&c <= '9'; c = gc()){x = x * 10 + c - '0';}return f ? -x : x; } int n,m; int Map[MAXN][MAXN]; int ReMap[MAXN][MAXN]; bool Mark[MAXN]; int A[MAXN]; int B[MAXN]; int EdgeIn[MAXN]; int Q_A[MAXN]; int lenA; int Q_B[MAXN]; int lenB; int Position[MAXN]; int Lis[MAXN]; int ans; bool Circle_Being; void ToplogicalSort_A(){memset(Mark,0,sizeof(Mark));queue<int>q;for(int i=1;i<=m;i++){if(!EdgeIn[A[i]]){q.push(A[i]); }}while(!q.empty()){int First=q.front();q.pop();Mark[First]=true;Q_A[++lenA]=First;for(int i=1;i<=m;i++){if(ReMap[First][A[i]]){ReMap[First][A[i]]=0;EdgeIn[A[i]]--;if(!EdgeIn[A[i]]){q.push(A[i]);}}}}if(lenA<m){//cout<<"A has circle"<<endl;Circle_Being=true;return ;} } void ToplogicalSort_B(){memset(Mark,0,sizeof(Mark));queue<int>q;for(int i=1;i<=B[0];i++){if(!EdgeIn[B[i]]){q.push(B[i]);}}while(!q.empty()){int First=q.front();q.pop();Mark[First]=true;Q_B[++lenB]=First;for(int i=1;i<=B[0];i++){if(ReMap[First][B[i]]){ReMap[First][B[i]]=0;EdgeIn[B[i]]--;if(!EdgeIn[B[i]]){q.push(B[i]);}}}}if(lenB<B[0]){//cout<<"B has circle"<<endl;Circle_Being=true;} } int main(){n=Read();m=Read();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){Map[i][j]=Read();ReMap[i][j]=Map[i][j];}}for(int i=1;i<=m;i++){A[i]=Read();Mark[A[i]]=true;}for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){if(Map[A[i]][A[j]]){EdgeIn[A[j]]++;}}}for(int i=1;i<=n;i++){if(!Mark[i]){B[++B[0]]=i;}}for(int i=1;i<=B[0];i++){for(int j=1;j<=B[0];j++){if(Map[B[i]][B[j]]){EdgeIn[B[j]]++;}}}ToplogicalSort_A();ToplogicalSort_B();if(Circle_Being){printf("NO");return 0;}printf("YES ");//截止这里，就已经实现了用拓补排序判断是否存在环的情况。for(int j=1;j<=B[0];j++){Lis[j]=1;int i=1;while(Map[Q_A[i]][Q_B[j]]&&i<=m){i++;}Position[j]=i;bool Insert=false;for(int k=i;k<=m;k++){if(Map[Q_A[k]][Q_B[j]]){Insert=true;break;}}if(Insert){Position[j]=0;}}for(int i=1;i<=B[0];i++){if(!Position[i]){continue;}for(int j=1;j<i;j++){if(Position[j]<=Position[i]&&Position[j]){Lis[i]=max(Lis[i],Lis[j]+1);}}}for(int i=1;i<=B[0];i++){ans=max(ans,Lis[i]);}printf("%d",ans); }